{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Making A Large Island"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #depth-first-search #breadth-first-search #union-find #array #matrix"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #深度优先搜索 #广度优先搜索 #并查集 #数组 #矩阵"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: largestIsland"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #最大人工岛"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个大小为 <code>n x n</code> 二进制矩阵 <code>grid</code> 。<strong>最多</strong> 只能将一格 <code>0</code> 变成 <code>1</code> 。</p>\n",
    "\n",
    "<p>返回执行此操作后，<code>grid</code> 中最大的岛屿面积是多少？</p>\n",
    "\n",
    "<p><strong>岛屿</strong> 由一组上、下、左、右四个方向相连的 <code>1</code> 形成。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入: </strong>grid = [[1, 0], [0, 1]]\n",
    "<strong>输出:</strong> 3\n",
    "<strong>解释:</strong> 将一格0变成1，最终连通两个小岛得到面积为 3 的岛屿。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入: </strong>grid =<strong> </strong>[[1, 1], [1, 0]]\n",
    "<strong>输出:</strong> 4\n",
    "<strong>解释:</strong> 将一格0变成1，岛屿的面积扩大为 4。</pre>\n",
    "\n",
    "<p><strong>示例 3:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入: </strong>grid = [[1, 1], [1, 1]]\n",
    "<strong>输出:</strong> 4\n",
    "<strong>解释:</strong> 没有0可以让我们变成1，面积依然为 4。</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>n == grid.length</code></li>\n",
    "\t<li><code>n == grid[i].length</code></li>\n",
    "\t<li><code>1 <= n <= 500</code></li>\n",
    "\t<li><code>grid[i][j]</code> 为 <code>0</code> 或 <code>1</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [making-a-large-island](https://leetcode.cn/problems/making-a-large-island/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [making-a-large-island](https://leetcode.cn/problems/making-a-large-island/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[1,0],[0,1]]', '[[1,1],[1,0]]', '[[1,1],[1,1]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestIsland(self, grid: List[List[int]]) -> int:\n",
    "        # 一轮遍历，直接标记\n",
    "        umap=defaultdict(int)\n",
    "        m=len(grid)\n",
    "        n=len(grid[0])\n",
    "        direct=[(0,1),(0,-1),(1,0),(-1,0)]\n",
    "        # dfs\n",
    "        def bfs(grid,x,y,key):\n",
    "            nonlocal m,n,direct,umap\n",
    "            grid[x][y]=key\n",
    "            umap[key]+=1\n",
    "            q=deque()\n",
    "            q.append((x,y))\n",
    "            while q:\n",
    "                cx,cy=q.popleft()\n",
    "                for i in range(4):\n",
    "                    nx=cx+direct[i][0]\n",
    "                    ny=cy+direct[i][1]\n",
    "                    if nx<0 or ny<0 or nx>=m or ny>=n:\n",
    "                        continue\n",
    "                    if grid[nx][ny]==1:\n",
    "                        umap[key]+=1\n",
    "                        grid[nx][ny]=key\n",
    "                        q.append((nx,ny))\n",
    "        # 标记\n",
    "        key=2\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j]==1:\n",
    "                    bfs(grid,i,j,key)\n",
    "                    key+=1\n",
    "        result=0\n",
    "        # 遍历\n",
    "        for x in range(m):\n",
    "            for y in range(n):\n",
    "                if grid[x][y]==0:\n",
    "                    cur=1\n",
    "                    bank_k=set()\n",
    "                    for i in range(4):\n",
    "                        nx=x+direct[i][0]\n",
    "                        ny=y+direct[i][1]\n",
    "                        if nx<0 or ny<0 or nx>=m or ny>=n:\n",
    "                            continue\n",
    "                        else:\n",
    "                            bank_k.add(grid[nx][ny])\n",
    "                    for k in bank_k:\n",
    "                        cur+=umap[k]\n",
    "                    result=max(result,cur)\n",
    "        for k in umap:\n",
    "            result=max(result,umap[k])\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestIsland(self, grid: List[List[int]]) -> int:\n",
    "        def dfs(grid,i,j,index):\n",
    "            if not inArea(grid,i,j):\n",
    "                return 0\n",
    "            if grid[i][j]!=1:\n",
    "                return 0\n",
    "            grid[i][j] = index\n",
    "\n",
    "            return 1+dfs(grid, i-1, j,index)+dfs(grid, i+1, j,index)+dfs(grid, i, j-1,index)+dfs(grid, i, j+1,index)\n",
    "\n",
    "        def areacal(grid,i,j,area):\n",
    "            up = down = left = right =0\n",
    "            if inArea(grid,i-1,j):\n",
    "                up = grid[i-1][j]\n",
    "            if inArea(grid, i+1, j):\n",
    "                down = grid[i+1][j]\n",
    "            if inArea(grid, i, j-1):\n",
    "                left = grid[i][j-1]\n",
    "            if inArea(grid, i, j+1):\n",
    "                right = grid[i][j+1]\n",
    "            filt = [up,down,left,right]\n",
    "            filt = list(set(filt))\n",
    "            length = len(filt)\n",
    "            sum = 0\n",
    "            for i in range(length):\n",
    "                sum += area[filt[i]]\n",
    "            return sum+1\n",
    "            # if len(filt)>1:\n",
    "            #     area1 = filt[-1]\n",
    "            #     area2 = filt[-2]\n",
    "            #     return area[area2]+area[area1]+1\n",
    "            # else:\n",
    "            #     return filt[0]+1\n",
    "\n",
    "\n",
    "        def inArea(grid,i,j):\n",
    "            return 0<=i<len(grid) and 0<=j<len(grid[0])\n",
    "\n",
    "\n",
    "\n",
    "        if not grid:\n",
    "            return 0\n",
    "        row = col = len(grid)\n",
    "        ans =0\n",
    "        for i in range(row):\n",
    "            for j in range(col):\n",
    "                if grid[i][j] == 0:\n",
    "                    ans+=1\n",
    "        if ans == 0 or ans ==1:\n",
    "            return row*col\n",
    "\n",
    "        area =[0]*2\n",
    "        #记录面积\n",
    "        index = 2\n",
    "        for i in range(row):\n",
    "            for j in range(col):\n",
    "                if grid[i][j] == 1:\n",
    "                    area.append(dfs(grid,i,j,index))\n",
    "                    index+=1\n",
    "        maxarea = 0#用于记录最大人工岛的面积\n",
    "        for i in range(row):\n",
    "            for j in range(col):\n",
    "                if grid[i][j] == 0:\n",
    "                    maxarea = max(areacal(grid,i,j,area),maxarea)\n",
    "        return maxarea\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestIsland(self, grid: List[List[int]]) -> int:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        gird_area_list = []\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j]==1:\n",
    "                    grid[i][j] = str(len(gird_area_list))\n",
    "                    gird_area_list.append(1)\n",
    "\n",
    "                    cur_list = [(i,j)]\n",
    "                    while cur_list:\n",
    "                        cur_i,cur_j = cur_list.pop(0)\n",
    "                        for offset in [(0,1),(0,-1),(1,0),(-1,0)]:\n",
    "                            if (0<=cur_i+offset[0]<m) and (0<=cur_j+offset[1]<n):\n",
    "                                if (grid[cur_i+offset[0]][cur_j+offset[1]]==1):\n",
    "                                    gird_area_list[-1] += 1\n",
    "                                    grid[cur_i+offset[0]][cur_j+offset[1]] = grid[i][j]\n",
    "                                    cur_list.append((cur_i+offset[0], cur_j+offset[1]))\n",
    "        # print(grid)\n",
    "        # print(gird_area_list)\n",
    "        max_area = max(gird_area_list) if gird_area_list else 1\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j]==0:\n",
    "                    cur_area_set = set()\n",
    "                    for offset in [(0,1),(0,-1),(1,0),(-1,0)]:\n",
    "                        if (0<=i+offset[0]<m) and (0<=j+offset[1]<n):\n",
    "                            if (grid[i+offset[0]][j+offset[1]]!=0):\n",
    "                                cur_area_set.add(int(grid[i+offset[0]][j+offset[1]]))\n",
    "                    max_area = max(max_area, sum(gird_area_list[cur_area] for cur_area in cur_area_set)+1)\n",
    "        return max_area\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    this_area = None\n",
    "    dirs = [(0, 1), (1, 0), (-1, 0), (0, -1)]\n",
    "    visited = None\n",
    "\n",
    "    def largestIsland(self, grid: List[List[int]]) -> int:\n",
    "        self.visited = [[0] * len(grid) for _ in range(len(grid))]\n",
    "        island_id = 0\n",
    "        island_area = {}\n",
    "        for i in range(len(grid)):\n",
    "            for j in range(len(grid)):\n",
    "                if not self.visited[i][j] and grid[i][j] == 1:\n",
    "                    self.this_area = 1\n",
    "                    island_id += 1\n",
    "                    self.visited[i][j] = island_id\n",
    "\n",
    "                    self.bfs(i, j, grid, island_id)\n",
    "\n",
    "                    island_area[island_id] = self.this_area\n",
    "                    self.this_area = 0\n",
    "\n",
    "        result = None\n",
    "        for i in range(len(grid)):\n",
    "            for j in range(len(grid)):\n",
    "                if grid[i][j] == 0:\n",
    "                    if result is None:\n",
    "                        result = 0\n",
    "                    self.this_area = 1\n",
    "                    added_island = []\n",
    "                    for d in self.dirs:\n",
    "                        next_i, next_j = i + d[0], j + d[1]\n",
    "                        if not (0 <= next_i < len(grid)) or not (0 <= next_j < len(grid)):\n",
    "                            continue\n",
    "                        if self.visited[next_i][next_j] and \\\n",
    "                        self.visited[next_i][next_j] not in added_island:\n",
    "                            added_island.append(self.visited[next_i][next_j])\n",
    "                            self.this_area += island_area[self.visited[next_i][next_j]]\n",
    "                    result = max(result, self.this_area)\n",
    "        \n",
    "        if result is not None:\n",
    "            return result\n",
    "        else:\n",
    "            return len(grid) ** 2\n",
    "\n",
    "\n",
    "    def bfs(self, i, j, grid, island_id):\n",
    "        queue = deque([(i, j)])\n",
    "        while queue:\n",
    "            this_r, this_c = queue.popleft()\n",
    "            for d in self.dirs:\n",
    "                next_r, next_c = this_r + d[0], this_c + d[1]\n",
    "\n",
    "                if not (0 <= next_r < len(grid)) or not (0 <= next_c < len(grid)):\n",
    "                    continue\n",
    "\n",
    "                if not self.visited[next_r][next_c] and grid[next_r][next_c] == 1:\n",
    "                    self.visited[next_r][next_c] = island_id\n",
    "                    self.this_area += 1\n",
    "                    queue.append((next_r, next_c))\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.direction = [(0,1),(0,-1),(1,0),(-1,0)]\n",
    "        self.curarea = 0\n",
    "        self.area = [0]\n",
    "    def largestIsland(self, grid: List[List[int]]) -> int:\n",
    "        Nrow = len(grid)\n",
    "        Ncol = len(grid[0])\n",
    "        mark = [[0]*Ncol for _ in range(Nrow)]\n",
    "        curInd = 0\n",
    "        maxArea = 0 \n",
    "        for i in range(Nrow):\n",
    "            for j in range(Ncol):\n",
    "                if grid[i][j] == 1 and not mark[i][j]:\n",
    "                    curInd+=1\n",
    "                    mark[i][j] = curInd\n",
    "                    self.curarea = 1\n",
    "                    self.callback(grid, mark, i,j,Nrow,Ncol,curInd)\n",
    "                    self.area.append(self.curarea)\n",
    "        maxArea=max(self.area)          \n",
    "        for i in range(Nrow):\n",
    "            for j in range(Ncol):\n",
    "                indSet = set()\n",
    "                sumarea = 0 \n",
    "                if not mark[i][j]:\n",
    "                    \n",
    "                    for k in range(4):\n",
    "                        newx = i+self.direction[k][0]\n",
    "                        newy = j + self.direction[k][1]\n",
    "                        if newx in range(Nrow) and newy in range(Ncol):\n",
    "                            if not mark[newx][newy] in indSet:\n",
    "                                sumarea += self.area[mark[newx][newy]]\n",
    "                                indSet.add(mark[newx][newy])\n",
    "\n",
    "                maxArea = max(maxArea, sumarea+1)\n",
    "        return maxArea\n",
    "\n",
    "    def callback(self,grid, mark, curx,cury,Nrow,Ncol,curInd):\n",
    "        if grid[curx][cury]==0 or not mark[curx][cury]:\n",
    "            return\n",
    "        \n",
    "        for k in range(4):\n",
    "            newx = curx +self.direction[k][0]\n",
    "            newy = cury + self.direction[k][1]\n",
    "            if newx in range(Nrow) and newy in range(Ncol):\n",
    "                if grid[newx][newy] == 1 and not mark[newx][newy]:\n",
    "                    mark[newx][newy] = curInd\n",
    "                    self.curarea += 1\n",
    "                    self.callback(grid, mark, newx,newy,Nrow,Ncol,curInd)\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestIsland(self, grid: List[List[int]]) -> int:\n",
    "        def dfs(grid,i,j,n,id):\n",
    "            if i<0 or i==n or j<0 or j==n or grid[i][j]!=1:\n",
    "                return\n",
    "            grid[i][j]=id\n",
    "            dfs(grid,i-1,j,n,id)\n",
    "            dfs(grid,i+1,j,n,id)\n",
    "            dfs(grid,i,j-1,n,id)\n",
    "            dfs(grid,i,j+1,n,id)\n",
    "            \n",
    "        n=len(grid)\n",
    "        id=2\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if grid[i][j]==1:\n",
    "                    dfs(grid,i,j,n,id)\n",
    "                    id+=1\n",
    "        if id==2:                    \n",
    "            return 1\n",
    "                         \n",
    "        size=[0]*(id+1)\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                x=grid[i][j]\n",
    "                if x!=0:                \n",
    "                    size[x]+=1                \n",
    "        if size[2]==n*n:             \n",
    "            return n*n\n",
    "                       \n",
    "        res=0\n",
    "        visited=[False]*(id+1)        \n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                merge=1\n",
    "                if grid[i][j]==0:\n",
    "                    up=grid[i-1][j] if i-1>=0 else 0\n",
    "                    down=grid[i+1][j] if i+1<n else 0\n",
    "                    left=grid[i][j-1] if j-1>=0 else 0\n",
    "                    right=grid[i][j+1] if j+1<n else 0\n",
    "                   \n",
    "                    visited[up]=True\n",
    "                    merge+=size[up]\n",
    "                    if not visited[down]:\n",
    "                        visited[down]=True\n",
    "                        merge+=size[down]\n",
    "                    if not visited[left]:\n",
    "                        visited[left]=True\n",
    "                        merge+=size[left]\n",
    "                    if not visited[right]:\n",
    "                        visited[right]=True\n",
    "                        merge+=size[right]\n",
    "                    res=max(res,merge)\n",
    "                    \n",
    "                    visited[up]=False\n",
    "                    visited[down]=False\n",
    "                    visited[left]=False\n",
    "                    visited[right]=False\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.dirs = [[1,0],[0,1],[-1,0],[0,-1]]\n",
    "        self.count = 0\n",
    "    def dfs(self,x,y,grid,mark):\n",
    "        for dx,dy in self.dirs:\n",
    "            currx = dx+x\n",
    "            curry = dy+y\n",
    "            if currx<0 or currx>=len(grid) or curry<0 or curry>=len(grid[0]):\n",
    "                continue\n",
    "            if grid[currx][curry]==1:\n",
    "                grid[currx][curry]=mark\n",
    "                self.count += 1\n",
    "                self.dfs(currx,curry,grid,mark)\n",
    "\n",
    "    def largestIsland(self, grid: List[List[int]]) -> int:\n",
    "        hashmap = defaultdict(int)\n",
    "        mark = 2\n",
    "        area = 0\n",
    "        maxarea = 0\n",
    "        visited = set()\n",
    "        isallgrid = True\n",
    "        for i in range(len(grid)):\n",
    "            for j in range(len(grid[0])):\n",
    "                if grid[i][j]==1:\n",
    "                    self.count = 1\n",
    "                    grid[i][j]=mark\n",
    "                    self.dfs(i,j,grid,mark)\n",
    "                    hashmap[mark]=self.count\n",
    "                    mark+=1\n",
    "                if grid[i][j]==0:\n",
    "                    isallgrid=False\n",
    "        # print('grid',grid)\n",
    "        # print('hashmap',hashmap)\n",
    "        if isallgrid:\n",
    "            return len(grid)*len(grid[0])\n",
    "        for i in range(len(grid)):\n",
    "            for j in range(len(grid[0])):\n",
    "                area = 1\n",
    "                visited = set()\n",
    "                if grid[i][j]==0:\n",
    "                    for dx, dy in self.dirs:\n",
    "                        nearx = i+dx\n",
    "                        neary = j+dy\n",
    "                        if nearx<0 or nearx>=len(grid) or neary<0 or neary>=len(grid[0]):\n",
    "                            continue\n",
    "                        if grid[nearx][neary] in visited:\n",
    "                            continue\n",
    "                        # print(hashmap[grid[nearx][neary]])\n",
    "                        # print('area',area)\n",
    "                        \n",
    "                        area += hashmap[grid[nearx][neary]]\n",
    "                        visited.add(grid[nearx][neary])\n",
    "                        print('area',area)\n",
    "                print(area)\n",
    "                maxarea = max(area, maxarea)\n",
    "    \n",
    "        return maxarea\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestIsland(self, grid: List[List[int]]) -> int:\n",
    "        ## First, compute the area size of each island\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        idxIsland = 2 # Index the Islands from 2\n",
    "        markIsland = dict()\n",
    "\n",
    "        def inArea(i, j):\n",
    "            return 0 <= i < m and 0 <= j < n\n",
    "\n",
    "        def areaSize(idxIsland, i, j):\n",
    "            if not inArea(i, j):\n",
    "                return 0\n",
    "            if grid[i][j] != 1:\n",
    "                return 0\n",
    "            grid[i][j] = idxIsland\n",
    "            return 1 + areaSize(idxIsland, i-1, j) + areaSize(idxIsland, i+1, j) + areaSize(idxIsland, i, j-1) + areaSize(idxIsland, i, j+1)\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1:\n",
    "                    size = areaSize(idxIsland, i, j)\n",
    "                    markIsland[idxIsland] = size\n",
    "                    idxIsland += 1\n",
    "\n",
    "        if len(markIsland) == 0:\n",
    "            return 1\n",
    "\n",
    "        if max(markIsland.values()) == m * n:\n",
    "            return m * n\n",
    "\n",
    "        ## Second, check each sea pixel and its neighbor islands' size\n",
    "        def area_idx(i, j):\n",
    "            if inArea(i, j):\n",
    "                idx = grid[i][j]\n",
    "                if idx == 0:\n",
    "                    return 0, 0 \n",
    "                size = markIsland[idx]\n",
    "                return idx, size\n",
    "            return 0, 0\n",
    "        \n",
    "        #compute the total size of neihgbor Islands\n",
    "        def neighbor_areas(i, j):\n",
    "            areas_dict = dict()\n",
    "            moves = {(0, 1), (0, -1), (-1, 0), (1, 0)}\n",
    "            for move in moves:\n",
    "                r = i + move[0]\n",
    "                c = j + move[1]\n",
    "                idx, size = area_idx(r, c)\n",
    "                #save the area size of the neighbor islands\n",
    "                if idx not in areas_dict:\n",
    "                    areas_dict.update({idx: size})\n",
    "            return sum(areas_dict.values())\n",
    "\n",
    "        #compute the max area size with the extra sea connection\n",
    "        res = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 0:\n",
    "                    size = 1 + neighbor_areas(i, j)\n",
    "                    res = max(res, size)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestIsland(self, grid: List[List[int]]) -> int:\n",
    "        result = 0\n",
    "        mark = 2\n",
    "        count = 0\n",
    "        umap = {}\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        dirs = [[-1, 0], [0, 1], [1, 0], [0, -1]]\n",
    "        def dfs(x, y):\n",
    "            nonlocal count\n",
    "            count += 1\n",
    "            grid[x][y] = mark\n",
    "            for d in dirs:\n",
    "                nx = x + d[0]\n",
    "                ny = y + d[1]\n",
    "                if not (0 <= nx < m and 0 <= ny < n):\n",
    "                    continue\n",
    "                if grid[nx][ny] == 1:\n",
    "                    dfs(nx, ny)\n",
    "                    grid[x][y] = mark\n",
    "        all_land = True\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1:\n",
    "                    count = 0\n",
    "                    dfs(i, j)\n",
    "                    umap[mark] = count\n",
    "                    mark += 1\n",
    "                if grid[i][j] == 0:\n",
    "                    all_land = False\n",
    "        if all_land:\n",
    "            return n * m\n",
    "        near = set()\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                near.clear()\n",
    "                count = 1\n",
    "                if grid[i][j] == 0:\n",
    "                    for d in dirs:\n",
    "                        nx = i + d[0]\n",
    "                        ny = j + d[1]\n",
    "                        if not (0 <= nx < m and 0 <= ny < n):\n",
    "                            continue\n",
    "                        if grid[nx][ny] in near:\n",
    "                            continue\n",
    "                        if grid[nx][ny] != 0:\n",
    "                            count += umap[grid[nx][ny]]\n",
    "                            near.add(grid[nx][ny])\n",
    "                result = max(result, count)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestIsland(self, grid: List[List[int]]) -> int:\n",
    "        \"\"\"\n",
    "        对每个岛进行标记 标记的过程可以通过dfs 然后统计每个岛的面积 把他放入到一个哈希表中\n",
    "        然后对于每一个grid[i][j]=0 把它变为1后 计算和其相连岛屿的新面积 \n",
    "        \"\"\"\n",
    "        n = len(grid)\n",
    "        \n",
    "        dirs = [[1,0],[-1,0],[0,1],[0,-1]]\n",
    "        tag = 2\n",
    "        area = defaultdict(int) #统计每个岛屿的面积\n",
    "        def dfs(x,y):\n",
    "            grid[x][y] = tag\n",
    "            area[tag] += 1\n",
    "            for dx,dy in dirs:\n",
    "                if 0<=x+dx<n and 0<=y+dy<n and grid[x+dx][y+dy]==1:\n",
    "                    dfs(x+dx,y+dy)\n",
    "            \n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if grid[i][j]==1:#还未被标记的陆地\n",
    "                    dfs(i,j)\n",
    "                    tag += 1\n",
    "        rs = max(area.values()) if len(area)>0 else 0\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if grid[i][j]==0:#寻找海洋的位置\n",
    "                    newArea = 1\n",
    "                    seen = set()\n",
    "                    for dx,dy in dirs:\n",
    "                        if 0<=i+dx<n and 0<=j+dy<n and grid[i+dx][j+dy]!=0 and grid[i+dx][j+dy] not in seen:\n",
    "                            newArea += area[grid[i+dx][j+dy]]\n",
    "                            seen.add(grid[i+dx][j+dy])\n",
    "                    rs = max(rs,newArea)\n",
    "        return rs\n",
    "                            \n",
    "\n",
    "    \n",
    "    def find(self,p,x):\n",
    "        if p[x]!=x:\n",
    "            p[x] = self.find(p,p[x])\n",
    "        return p[x]\n",
    "\n",
    "    def union(self,p,sz,a,b):\n",
    "        ra,rb = self.find(p,a),self.find(p,b)\n",
    "        if ra!=rb:#不是同一个祖先 需合并\n",
    "            if sz[ra]>sz[rb]: #方便统一操作\n",
    "                ra,rb = rb,ra\n",
    "            sz[rb] += sz[ra] #大的吞并小的\n",
    "            p[ra] = p[rb]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def setArea(self, grid, flag, area, i, j, num, curr_area):\n",
    "        if i < 0 or j < 0 or i >= len(grid) or j >= len(grid[0]):\n",
    "            return\n",
    "        if grid[i][j] == 0 or flag[i][j] != num or area[i][j] == curr_area:\n",
    "            return\n",
    "        area[i][j] = curr_area\n",
    "        self.setArea(grid, flag, area, i + 1, j, num, curr_area)\n",
    "        self.setArea(grid, flag, area, i - 1, j, num, curr_area)\n",
    "        self.setArea(grid, flag, area, i, j + 1, num, curr_area)\n",
    "        self.setArea(grid, flag, area, i, j - 1, num, curr_area)\n",
    "\n",
    "    def dfs(self, grid, flag, i, j, num):\n",
    "        if i < 0 or j < 0 or i >= len(grid) or j >= len(grid[0]):\n",
    "            return 0\n",
    "        if grid[i][j] == 0 or flag[i][j] != 0:\n",
    "            return 0\n",
    "        flag[i][j] = num\n",
    "        return 1 + self.dfs(grid, flag, i + 1, j, num) + self.dfs(grid, flag, i - 1, j, num) + self.dfs(grid, flag, i, j + 1, num) + self.dfs(grid, flag, i, j - 1, num)\n",
    "\n",
    "    def largestIsland(self, grid: List[List[int]]) -> int:\n",
    "        result = 0\n",
    "        num = 1\n",
    "        flag = [[0] * len(grid[0]) for _ in range(len(grid))]\n",
    "        area = [[0] * len(grid[0]) for _ in range(len(grid))]\n",
    "        for i in range(len(grid)):\n",
    "            for j in range(len(grid[0])):\n",
    "                if grid[i][j] == 0 or flag[i][j] != 0:\n",
    "                    continue\n",
    "                curr_area = self.dfs(grid, flag, i, j, num)\n",
    "                result = max(result, curr_area)\n",
    "                self.setArea(grid, flag, area, i, j, num, curr_area)\n",
    "                num += 1\n",
    "        for i in range(len(grid)):\n",
    "            for j in range(len(grid[0])):\n",
    "                if grid[i][j] == 1:\n",
    "                    continue\n",
    "                m = {}\n",
    "                if i > 0:\n",
    "                    m[flag[i - 1][j]] = area[i - 1][j]\n",
    "                if i < len(grid) - 1:\n",
    "                    m[flag[i + 1][j]] = area[i + 1][j]\n",
    "                if j > 0:\n",
    "                    m[flag[i][j - 1]] = area[i][j - 1]\n",
    "                if j < len(grid[0]) - 1:\n",
    "                    m[flag[i][j + 1]] = area[i][j + 1]\n",
    "                area_sum = 0\n",
    "                for k in m:\n",
    "                    area_sum += m[k]\n",
    "                result = max(result, area_sum + 1)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestIsland(self, grid: List[List[int]]) -> int:\n",
    "        len_edge = len(grid)\n",
    "        if len_edge == 1:\n",
    "            return 1\n",
    "        import collections\n",
    "        island_area = collections.defaultdict(int)\n",
    "        island_idx = -1\n",
    "        \n",
    "        def dfs_set_island(x, y, set_idx):\n",
    "            grid[x][y] = set_idx\n",
    "            island_area[set_idx] += 1\n",
    "\n",
    "            for n_x, n_y in (x-1, y),(x+1, y),(x, y-1),(x, y+1):\n",
    "                if 0 <= n_x < len_edge and 0 <= n_y < len_edge and grid[n_x][n_y] == 1:\n",
    "                    dfs_set_island(n_x, n_y, set_idx) \n",
    "\n",
    "        for r_idx, row in enumerate(grid):\n",
    "            for c_idx, val in enumerate(row):\n",
    "                if val == 1:\n",
    "                    dfs_set_island(r_idx, c_idx, island_idx)\n",
    "                    island_idx -= 1\n",
    "        \n",
    "        ret_area = 1\n",
    "        for _, v in island_area.items():\n",
    "            ret_area = max(ret_area, v)\n",
    "        \n",
    "        for r_idx, row in enumerate(grid):\n",
    "            for c_idx, val in enumerate(row):\n",
    "                if val == 0:\n",
    "                    n_island_idx = list()\n",
    "                    for n_x, n_y in (r_idx+1, c_idx),(r_idx-1, c_idx),(r_idx, c_idx-1),(r_idx, c_idx+1):\n",
    "                        if 0 <= n_x < len_edge and 0 <= n_y < len_edge and grid[n_x][n_y] < 0:\n",
    "                            n_island_idx.append(grid[n_x][n_y])\n",
    "                    if len(n_island_idx) > 0:\n",
    "                        n_island_idx = set(n_island_idx)\n",
    "                        ret_area = max(ret_area, sum([island_area[island_idx] for island_idx in n_island_idx]) + 1)\n",
    "        \n",
    "        return ret_area\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestIsland(self, grid: List[List[int]]) -> int:\n",
    "\n",
    "        def dfs(grid, i, j, label):\n",
    "            m, n = len(grid), len(grid[0])\n",
    "\n",
    "            grid[i][j] = label\n",
    "            dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]]\n",
    "            \n",
    "            area = 1\n",
    "            for dir in dirs:\n",
    "                x = i + dir[0]\n",
    "                y = j + dir[1]\n",
    "\n",
    "                if x < 0 or x >= m or y < 0 or y >= n:\n",
    "                    continue\n",
    "                \n",
    "                if grid[x][y] == 1 :\n",
    "                    print(x, y)\n",
    "                    grid[x][y] = label\n",
    "                    area += dfs(grid, x, y, label)\n",
    "            return area\n",
    "\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        \n",
    "        label = 2\n",
    "        map_dict = {}\n",
    "        max_area = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1:\n",
    "                    area = dfs(grid, i, j, label)\n",
    "                    map_dict[label] = area\n",
    "                    max_area = max(max_area, area)\n",
    "                    label += 1\n",
    "        \n",
    "        print(grid)\n",
    "        print(map_dict)\n",
    "\n",
    "        dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]]\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 0:\n",
    "                    temp_area = 0\n",
    "                    visit_label = []\n",
    "                    for dir in dirs:\n",
    "                        x, y = i + dir[0], j + dir[1]\n",
    "                        if x < 0 or x >= m or y < 0 or y >= n:\n",
    "                            continue\n",
    "                        if grid[x][y] in map_dict and grid[x][y] not in visit_label:\n",
    "                            temp_area += map_dict[grid[x][y]]\n",
    "                            visit_label.append(grid[x][y])\n",
    "\n",
    "                    max_area = max(max_area, temp_area + 1)\n",
    "\n",
    "        return max_area\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestIsland(self, grid: List[List[int]]) -> int:\n",
    "        def dfs(x, y):\n",
    "            nonlocal area\n",
    "            if not 0<=x<m or not 0<=y<n or grid[x][y] != 1:\n",
    "                return\n",
    "            area += 1\n",
    "            grid[x][y] = len(ans) + 2\n",
    "            dfs(x-1, y)\n",
    "            dfs(x+1, y)\n",
    "            dfs(x, y-1)\n",
    "            dfs(x, y+1)\n",
    "        \n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        ans = []\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1:\n",
    "                    area = 0\n",
    "                    dfs(i, j)\n",
    "                    ans.append(area)\n",
    "        if ans:\n",
    "            if max(ans) == m*n:\n",
    "                return m*n\n",
    "            if max(ans) == 0:\n",
    "                return 1\n",
    "\n",
    "        result = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 0:\n",
    "                    temp = 1\n",
    "                    hashset = set()\n",
    "                    for x, y in [(i-1, j), (i+1, j), (i, j-1), (i, j+1)]:\n",
    "                        if 0<=x<m and 0<=y<n and grid[x][y] != 0 and grid[x][y] not in hashset: \n",
    "                            hashset.add(grid[x][y])\n",
    "                            temp += ans[grid[x][y] - 2]\n",
    "                    result = max(result, temp)\n",
    "        \n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestIsland(self, grid: List[List[int]]) -> int:\n",
    "        def dfs(grid, r, c, flag):  # 统计每个岛屿的面积\n",
    "            if not grid or r < 0 or r >= len(grid) or c < 0 or c >= len(grid[0]) or grid[r][c] != 1:\n",
    "                return 0\n",
    "\n",
    "            grid[r][c] = flag\n",
    "\n",
    "            c1 = dfs(grid, r + 1, c, flag)\n",
    "            c2 = dfs(grid, r - 1, c, flag)\n",
    "            c3 = dfs(grid, r, c + 1, flag)\n",
    "            c4 = dfs(grid, r, c - 1, flag)\n",
    "            return c1 + c2 + c3 + c4 + 1\n",
    "\n",
    "        def get_edge_num(grid, r, c):\n",
    "            if not grid or r < 0 or r >= len(grid) or c < 0 or c >= len(grid[0]) or grid[r][c] != 0:\n",
    "                return {}\n",
    "            edges = set()\n",
    "            edges.add(grid[r + 1][c] if 0 <= r + 1 < len(grid) else 0)\n",
    "            edges.add(grid[r - 1][c] if 0 <= r - 1 < len(grid) else 0)\n",
    "            edges.add(grid[r][c + 1] if 0 <= c + 1 < len(grid[0]) else 0)\n",
    "            edges.add(grid[r][c - 1] if 0 <= c - 1 < len(grid[0]) else 0)\n",
    "            return edges\n",
    "\n",
    "        if not grid or not grid[0]:  # 为空\n",
    "            return 0\n",
    "\n",
    "        if max(max(grid)) == 0:  # 全为0\n",
    "            return 1\n",
    "\n",
    "        if min(min(grid)) == 1:  # 全为1\n",
    "            return len(grid) * len(grid[0])\n",
    "\n",
    "        flag = -1\n",
    "        squares = dict()\n",
    "        for i in range(len(grid)):\n",
    "            for j in range(len(grid[0])):\n",
    "                if grid[i][j] == 1:\n",
    "                    squares[flag] = dfs(grid, i, j, flag)\n",
    "                    flag -= 1\n",
    "        edges = set()\n",
    "        for i in range(len(grid)):\n",
    "            for j in range(len(grid[0])):\n",
    "                edge = get_edge_num(grid, i, j)\n",
    "                edges.add(tuple(edge))\n",
    "\n",
    "        max_square = 0\n",
    "        for edge in list(edges):\n",
    "            square = 1\n",
    "            for e in edge:\n",
    "                square += squares.get(e, 0)\n",
    "            max_square = square if max_square < square else max_square\n",
    "\n",
    "        return max_square"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self, grid):\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        self.max = 0\n",
    "        self.father = [0] * m * n\n",
    "        self.value = [0] * m * n\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                k = i * n + j\n",
    "                if grid[i][j]:\n",
    "                    self.father[k] = k\n",
    "                    self.value[k] = 1\n",
    "                    self.max = 1\n",
    "                    \n",
    "    def find(self, x: int):\n",
    "        if x == self.father[x]:\n",
    "            return x\n",
    "        self.father[x] = self.find(self.father[x])\n",
    "        return self.father[x]\n",
    "\n",
    "    def merge(self, i: int, j: int):\n",
    "        x, y = self.find(i), self.find(j)\n",
    "        if x != y:\n",
    "            if self.value[y] <= self.value[x]:\n",
    "                self.father[y] = x\n",
    "                self.value[x] += self.value[y]\n",
    "                self.max = max(self.max, self.value[x])\n",
    "            else:\n",
    "                self.father[x] = y\n",
    "                self.value[y] += self.value[x]\n",
    "                self.max = max(self.max, self.value[y])\n",
    " \n",
    "class Solution:\n",
    "    def largestIsland(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        uf = UnionFind(grid)\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                k = i * n + j\n",
    "                if grid[i][j]:\n",
    "                    if j < n - 1 and grid[i][j+1]:\n",
    "                        uf.merge(k, k+1)\n",
    "                    if i < m - 1 and grid[i+1][j]:\n",
    "                        uf.merge(k, k+n)\n",
    "        ret = uf.max\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                k = i * n + j\n",
    "                if grid[i][j] == 0:\n",
    "                    cnt = Counter()\n",
    "                    if i > 0 and grid[i-1][j]:\n",
    "                        cnt[uf.find((i-1)*n+j)] = uf.value[uf.find((i-1)*n+j)]\n",
    "                    if j > 0 and grid[i][j-1]:\n",
    "                        cnt[uf.find(i*n+j-1)] = uf.value[uf.find(i*n+j-1)]\n",
    "                    if i < m - 1 and grid[i+1][j]:\n",
    "                        cnt[uf.find((i+1)*n+j)] = uf.value[uf.find((i+1)*n+j)]\n",
    "                    if j < n - 1 and grid[i][j+1]:\n",
    "                        cnt[uf.find(i*n+j+1)] = uf.value[uf.find(i*n+j+1)]\n",
    "                    ret = max(ret, sum(cnt.values()) + 1)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.count = 0\n",
    "    def largestIsland(self, grid: List[List[int]]) -> int:\n",
    "        m,n = len(grid), len(grid[0])\n",
    "        visited = [[False]*n for _ in range(m)]\n",
    "        gridNum = dict()\n",
    "        gridNum[0] = 0\n",
    "        mark = 2\n",
    "        isAllGrid = True\n",
    "        isAllocean = True\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 0: isAllGrid = False\n",
    "                if grid[i][j] == 1: isAllocean = False\n",
    "                if not visited[i][j] and grid[i][j] == 1:\n",
    "                    self.count = 0\n",
    "                    self.dfs(grid,i,j,visited,mark)\n",
    "                    gridNum[mark] = self.count\n",
    "                    mark += 1\n",
    "        if isAllGrid:\n",
    "            return m*n\n",
    "        if isAllocean:\n",
    "            return 1\n",
    "        res = 0\n",
    "        visitedGrid = set()\n",
    "        print(grid)\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                visitedGrid.clear()\n",
    "                self.count = 1\n",
    "                if grid[i][j] == 0:\n",
    "                    for new_i, new_j in [[i+1,j],[i,j+1],[i-1,j],[i,j-1]]:\n",
    "                        if 0<=new_i<len(grid) and 0<=new_j<len(grid[0]) and grid[new_i][new_j] not in visitedGrid:\n",
    "                            # print(grid[new_i][new_j])\n",
    "                            self.count += gridNum[grid[new_i][new_j]]\n",
    "                            visitedGrid.add(grid[new_i][new_j])\n",
    "                res = max(res,self.count)\n",
    "        return res\n",
    "\n",
    "\n",
    "    \n",
    "    def dfs(self,grid,x,y,visited,mark):\n",
    "        if visited[x][y] or grid[x][y] == 0:\n",
    "             return\n",
    "        visited[x][y] = True\n",
    "        grid[x][y] = mark\n",
    "        self.count+=1\n",
    "        for new_x, new_y in [[x+1,y],[x,y+1],[x-1,y],[x,y-1]]:\n",
    "            if new_x < 0 or new_x >= len(grid) or new_y < 0 or new_y >= len(grid[0]): continue\n",
    "            self.dfs(grid, new_x, new_y, visited, mark)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestIsland(self, grid: List[List[int]]) -> int:\n",
    "        \"\"\"\n",
    "        在遍历岛屿的时候，给每个位置记录它所在岛屿的面积；\n",
    "        要想在dfs的时候直接返回面积比较难，可以在dfs的时候先给一个编号，再记录该编号对应的面积:\n",
    "        (i, j)->mark->s\n",
    "        这样在修改时，只需要累加周围岛屿的面积即可\n",
    "        \"\"\"\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        def dfs(x, y, mark):\n",
    "            nonlocal cnt\n",
    "            cnt += 1\n",
    "            grid[x][y] = mark\n",
    "            for nx, ny in [(x+1, y), (x-1, y), (x, y+1), (x, y-1)]:\n",
    "                if 0<=nx<m and 0<=ny<n and grid[nx][ny] == 1:\n",
    "                    dfs(nx, ny, mark)\n",
    "        mark = 2\n",
    "        areas = {}\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1:\n",
    "                    cnt = 0\n",
    "                    dfs(i, j, mark)\n",
    "                    areas[mark] = cnt\n",
    "                    mark += 1\n",
    "        print(grid)\n",
    "        res = max(areas.values()) if mark > 2 else 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 0:\n",
    "                    x, y = i, j\n",
    "                    totals = 1\n",
    "                    used = []\n",
    "                    for nx, ny in [(x+1, y), (x-1, y), (x, y+1), (x, y-1)]:\n",
    "                        if 0<=nx<m and 0<=ny<n and grid[nx][ny] >= 2 and grid[nx][ny] not in used:\n",
    "                            totals += areas[grid[nx][ny]]\n",
    "                            used.append(grid[nx][ny])\n",
    "                    res = max(res, totals)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.position = [[-1,0],[0,1],[1,0],[0,-1]]\n",
    "    def largestIsland(self, grid: List[List[int]]) -> int:\n",
    "        n = len(grid)\n",
    "        visited = [[0] * n for _ in range(n)]\n",
    "        counter = 0\n",
    "        cnt = Counter()\n",
    "        def dfs(i: int, j: int) -> None:\n",
    "            if visited[i][j] and grid[i][j] == 0:\n",
    "                return\n",
    "            cnt[counter] += 1\n",
    "            visited[i][j] = counter\n",
    "            for p in self.position:\n",
    "                x,y = i + p[0],j + p[1]\n",
    "                if 0 <= x < n and 0 <= y < n and grid[x][y] and visited[x][y] == False:\n",
    "                    dfs(x, y)\n",
    "        for i, row in enumerate(grid):\n",
    "            for j, x in enumerate(row):\n",
    "                if x and visited[i][j] == False: \n",
    "                    counter += 1\n",
    "                    dfs(i,j)\n",
    "        ans = max(cnt.values(),default=0)\n",
    "\n",
    "        for i, row in enumerate(grid):\n",
    "            for j, x in enumerate(row):\n",
    "                if x == 0:  \n",
    "                    new_area = 1\n",
    "                    connected = {0}\n",
    "                    for p in self.position:\n",
    "                        x,y = i + p[0],j + p[1]\n",
    "                        if 0 <= x < n and 0 <= y < n and visited[x][y] not in connected:\n",
    "                            new_area += cnt[visited[x][y]]\n",
    "                            connected.add(visited[x][y])\n",
    "                    ans = max(ans, new_area)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestIsland(self, grid) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "\n",
    "        area_list = [[0] * m for _ in range(n)]\n",
    "        area_dict = {}\n",
    "        island_idx = 2\n",
    "\n",
    "        def dfs(i, j):\n",
    "            if i < 0 or i >= m or j < 0 or j >= n or grid[i][j] != 1:\n",
    "                return 0\n",
    "            grid[i][j] = island_idx\n",
    "\n",
    "            return 1 + dfs(i - 1, j) + dfs(i + 1, j) + dfs(i, j - 1) + dfs(i, j + 1)\n",
    "        ans = 0\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1:\n",
    "                    this_area = dfs(i, j)\n",
    "                    area_dict[island_idx] = this_area\n",
    "                    ans = max(ans, this_area)\n",
    "                    island_idx += 1\n",
    "\n",
    "\n",
    "        def check_near(i, j):\n",
    "            new_area = 1\n",
    "            directions = [[-1, 0], [1, 0], [0, 1], [0, -1]]\n",
    "            temp_list = []\n",
    "            for one_dir in directions:\n",
    "                new_i, new_j = i + one_dir[0], j + one_dir[1]\n",
    "                if 0 <= new_i < m and 0 <= new_j < n and grid[new_i][new_j] >= 2 and grid[new_i][new_j] not in temp_list:\n",
    "                    new_area += area_dict[grid[new_i][new_j]]\n",
    "                    temp_list.append(grid[new_i][new_j])\n",
    "\n",
    "            return new_area\n",
    "\n",
    "\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 0:\n",
    "                    ans = max(ans, check_near(i, j))\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestIsland(self, grid: List[List[int]]) -> int:\n",
    "        m = len(grid)\n",
    "        if m < 1:\n",
    "            return 0\n",
    "        n = len(grid[0])\n",
    "        \n",
    "        def helper(grid, i, j, m, n, idx, locs):\n",
    "            if i < 0 or i >= m or j < 0 or j >= n or grid[i][j] != 1:\n",
    "                return 0\n",
    "            locs.append((i, j))\n",
    "            grid[i][j] = idx\n",
    "            ret = 1\n",
    "            ret += helper(grid, i - 1, j, m, n, idx, locs)\n",
    "            ret += helper(grid, i + 1, j, m, n, idx, locs)\n",
    "            ret += helper(grid, i, j - 1, m, n, idx, locs)\n",
    "            ret += helper(grid, i, j + 1, m, n, idx, locs)\n",
    "            return ret\n",
    "\n",
    "        island_idx = 2\n",
    "        loc_area_rec = [[(-1, 0) for _ in range(n)] for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1:\n",
    "                    locs = []\n",
    "                    area = helper(grid, i, j, m, n, island_idx, locs)\n",
    "                    for x, y in locs:\n",
    "                        loc_area_rec[x][y] = (island_idx, area)\n",
    "                    island_idx += 1\n",
    "        \n",
    "        max_join_area = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] != 0:\n",
    "                    continue\n",
    "                \n",
    "                cur_join_area = 0\n",
    "                adj_idx_set = set()\n",
    "                for x, y in ((i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)):\n",
    "                    if 0 <= x < m and 0 <= y < n:\n",
    "                        idx, area = loc_area_rec[x][y]\n",
    "                        if idx != -1 and idx not in adj_idx_set:\n",
    "                            adj_idx_set.add(idx)\n",
    "                            cur_join_area += area\n",
    "                cur_join_area += 1\n",
    "                max_join_area = max(max_join_area, cur_join_area)\n",
    "\n",
    "        max_join_area = max(max_join_area, loc_area_rec[0][0][1])\n",
    "\n",
    "        return max_join_area"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestIsland(self, grid: List[List[int]]) -> int:\n",
    "        n=len(grid)\n",
    "        visited=[[False for _ in range(n)] for _ in range(n)]\n",
    "        area=[[(-1,0) for _ in range(n)] for _ in range(n)]\n",
    "        self.aid=0\n",
    "        def visit(i,j):\n",
    "            q=[(i,j)]\n",
    "            visited[i][j]=True\n",
    "            num=0\n",
    "            while len(q):\n",
    "                ni,nj=q[0]\n",
    "                num+=1\n",
    "                if 0<=ni+1<n and grid[ni+1][nj]==1 and visited[ni+1][nj]==False:\n",
    "                    visited[ni+1][nj]=True\n",
    "                    q.append((ni+1,nj))\n",
    "                if 0<=ni-1<n and grid[ni-1][nj]==1 and visited[ni-1][nj]==False:\n",
    "                    visited[ni-1][nj]=True\n",
    "                    q.append((ni-1,nj))\n",
    "                if 0<=nj+1<n and grid[ni][nj+1]==1 and visited[ni][nj+1]==False:\n",
    "                    visited[ni][nj+1]=True\n",
    "                    q.append((ni,nj+1))\n",
    "                if 0<=nj-1<n and grid[ni][nj-1]==1 and visited[ni][nj-1]==False:\n",
    "                    visited[ni][nj-1]=True\n",
    "                    q.append((ni,nj-1))\n",
    "                q.pop(0)\n",
    "            q=[(i,j)]\n",
    "            area[i][j]=(self.aid, num)\n",
    "            while len(q):\n",
    "                ni,nj=q[0]\n",
    "                if 0<=ni+1<n and grid[ni+1][nj]==1 and area[ni+1][nj][1]==0:\n",
    "                    area[ni+1][nj]=(self.aid, num)\n",
    "                    q.append((ni+1,nj))\n",
    "                if 0<=ni-1<n and grid[ni-1][nj]==1 and area[ni-1][nj][1]==0:\n",
    "                    area[ni-1][nj]=(self.aid, num)\n",
    "                    q.append((ni-1,nj))\n",
    "                if 0<=nj+1<n and grid[ni][nj+1]==1 and area[ni][nj+1][1]==0:\n",
    "                    area[ni][nj+1]=(self.aid, num)\n",
    "                    q.append((ni,nj+1))\n",
    "                if 0<=nj-1<n and grid[ni][nj-1]==1 and area[ni][nj-1][1]==0:\n",
    "                    area[ni][nj-1]=(self.aid, num)\n",
    "                    q.append((ni,nj-1))\n",
    "                q.pop(0)\n",
    "            self.aid+=1\n",
    "            return num\n",
    "\n",
    "        m=0\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if grid[i][j]==1 and visited[i][j]==False: m=max(m, visit(i,j))\n",
    "        # print(grid, area, visited)\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if grid[i][j]==0:\n",
    "                    ma=1\n",
    "                    s=set()\n",
    "                    if 0<=i+1<n and (area[i+1][j][0] not in s):\n",
    "                        ma+=area[i+1][j][1]\n",
    "                        s.add(area[i+1][j][0])\n",
    "                    if 0<=i-1<n and (area[i-1][j][0] not in s):\n",
    "                        ma+=area[i-1][j][1]\n",
    "                        s.add(area[i-1][j][0])\n",
    "                    if 0<=j+1<n and (area[i][j+1][0] not in s):\n",
    "                        ma+=area[i][j+1][1]\n",
    "                        s.add(area[i][j+1][0])\n",
    "                    if 0<=j-1<n and (area[i][j-1][0] not in s):\n",
    "                        ma+=area[i][j-1][1]\n",
    "                        s.add(area[i][j-1][0])\n",
    "                    if ma>m: m=ma\n",
    "        return m"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestIsland(self, grid: List[List[int]]) -> int:\n",
    "        board_i, board_j = len(grid), len(grid[0])\n",
    "        visited = [[False for _ in range(board_j)]  for _ in range(board_i)]\n",
    "        gridNum = dict()\n",
    "        def dfs(cur_i, cur_j, mark):\n",
    "            if not 0 <= cur_i < board_i or not 0 <= cur_j < board_j or visited[cur_i][cur_j] or grid[cur_i][cur_j] == 0:\n",
    "                return 0\n",
    "            visited[cur_i][cur_j] = True\n",
    "            grid[cur_i][cur_j] = mark\n",
    "            cnt = 1\n",
    "            for di, dj in [[0, 1], [0, -1], [1, 0], [-1, 0]]:\n",
    "                next_i, next_j = cur_i + di, cur_j + dj\n",
    "                cnt = cnt + dfs(next_i, next_j, mark)\n",
    "            return cnt\n",
    "        mark = 2\n",
    "        isAllland = True\n",
    "\n",
    "        for i in range(0, board_i):\n",
    "            for j in range(0, board_j):\n",
    "                if grid[i][j] == 0:\n",
    "                    isAllland =False\n",
    "                if not visited[i][j] and grid[i][j] == 1:\n",
    "                    gridNum[mark] = dfs(i, j, mark)\n",
    "                    mark = mark + 1\n",
    "        if isAllland:\n",
    "            return board_i * board_j\n",
    "        res = 0\n",
    "        visitedgrid = set()\n",
    "\n",
    "        for i in range(board_i):\n",
    "            for j in range(board_j):\n",
    "                ans = 1\n",
    "                visitedgrid.clear()\n",
    "                if grid[i][j] == 0:\n",
    "                    for di, dj in [[0, 1], [0, -1], [1, 0], [-1, 0]]:\n",
    "                        next_i, next_j = i + di, j + dj\n",
    "                        if not 0 <= next_i < board_i or not 0 <= next_j < board_j:\n",
    "                            continue\n",
    "                        if grid[next_i][next_j] in visitedgrid:\n",
    "                            continue\n",
    "                        if grid[next_i][next_j] != 0:\n",
    "                            ans = ans + gridNum[grid[next_i][next_j]]\n",
    "                            visitedgrid.add(grid[next_i][next_j])\n",
    "                res = max(res, ans)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "class DisjointSet:\n",
    "    def __init__(self, n):\n",
    "        self.n = n\n",
    "        self.g = []\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                self.g.append(i*n + j)\n",
    "        self.compress = True\n",
    "\n",
    "    def join(self, x1, y1, x2, y2):\n",
    "        if self.find(x1, y1) == self.find(x2, y2):\n",
    "            return False\n",
    "        p1 = self.find(x1, y1)\n",
    "        p2 = self.find(x2, y2)\n",
    "        self.g[p1] = p2\n",
    "        return True\n",
    "\n",
    "    def callback(self, x, y):\n",
    "        pass\n",
    "\n",
    "    def find(self, x, y):\n",
    "        z = x*self.n + y\n",
    "        if self.g[z] == z:\n",
    "            return z\n",
    "        else:\n",
    "            x2 = self.g[z] // self.n\n",
    "            y2 = self.g[z] % self.n\n",
    "            if self.compress:    \n",
    "                self.g[z] = self.find(x2, y2)\n",
    "                return self.g[z]\n",
    "            else:\n",
    "                return self.find(x2, y2)\n",
    "\n",
    "directions = [\n",
    "    (1, 0),\n",
    "    (-1, 0),\n",
    "    (0, 1),\n",
    "    (0, -1)\n",
    "]\n",
    "\n",
    "class Solution:\n",
    "    def largestIsland(self, grid: List[List[int]]) -> int:\n",
    "        n = len(grid)\n",
    "        js = DisjointSet(n)\n",
    "        for i, row in enumerate(grid):\n",
    "            for j, col in enumerate(row):\n",
    "                if col == 0:\n",
    "                    continue\n",
    "                for dx, dy in directions:\n",
    "                    x = i+dx\n",
    "                    y = j+dy\n",
    "                    if 0 <= x < n and 0 <= y < n:\n",
    "                        if grid[x][y] == 1:\n",
    "                            js.join(i, j, x, y)\n",
    "        bridges = []\n",
    "        gc = defaultdict(int)\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 0:\n",
    "                    continue\n",
    "                group = js.find(i, j)\n",
    "                gc[group] += 1\n",
    "        # print(gc)\n",
    "        if not gc:\n",
    "            ans = 1\n",
    "        else:\n",
    "            ans = max(gc.values()) + 1\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1:\n",
    "                    continue\n",
    "                add_groups = set()\n",
    "                for dx, dy in directions:\n",
    "                    x = i + dx\n",
    "                    y = j + dy\n",
    "                    if 0 <= x < n and 0 <= y < n and grid[x][y] == 1:\n",
    "                        add_groups.add(js.find(x, y))\n",
    "                total = 1\n",
    "                for gg in add_groups:\n",
    "                    total += gc[gg]\n",
    "                if total > ans:\n",
    "                    # print(i, j, total, add_groups)\n",
    "                    ans = total\n",
    "        # print(gc)\n",
    "        # print(js.g)\n",
    "        return min(ans, n*n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestIsland(self, grid: List[List[int]]) -> int:\n",
    "        res=0\n",
    "        res_dict={0:0}\n",
    "\n",
    "        m,n = len(grid), len(grid[0])\n",
    "        visited=[[0 for _ in range(n)] for _ in range(m)]\n",
    "        path=[[0,1],[0,-1],[1,0],[-1,0]]\n",
    "\n",
    "        def dfs(x,y,res_this,mark):\n",
    "            for p in path:\n",
    "                newx=x+p[0]\n",
    "                newy=y+p[1]\n",
    "\n",
    "                if newx<0 or newy<0 or newx>m-1 or newy>n-1:\n",
    "                    continue\n",
    "\n",
    "                if grid[newx][newy]==1 and visited[newx][newy]==0:\n",
    "                    visited[newx][newy]=mark\n",
    "                    res_this+=1\n",
    "                    res_this=dfs(newx,newy,res_this,mark)\n",
    "            \n",
    "            return res_this\n",
    "\n",
    "        mark=1\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j]==1 and visited[i][j]==0:\n",
    "                    visited[i][j]=mark\n",
    "                    res_this=1\n",
    "                    res_dict[mark]=dfs(i,j,res_this,mark)\n",
    "                    mark+=1\n",
    "        \n",
    "        # print(visited,res_dict)\n",
    "        \n",
    "        is0=False\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j]==0:\n",
    "                    is0=True\n",
    "                    mark_add={}\n",
    "                    res_this=1\n",
    "                    for p in path:\n",
    "                        newx=i+p[0]\n",
    "                        newy=j+p[1]\n",
    "                        if newx<0 or newy<0 or newx>m-1 or newy>n-1:\n",
    "                            continue\n",
    "                        \n",
    "                        if visited[newx][newy] not in mark_add:\n",
    "                            res_this+=res_dict[visited[newx][newy]]\n",
    "                        mark_add[visited[newx][newy]]=1\n",
    "                    res=max(res,res_this)\n",
    "\n",
    "        if is0==False:\n",
    "            return res_dict[1]\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestIsland(self, grid: List[List[int]]) -> int:\n",
    "        n = len(grid)\n",
    "        judge = []\n",
    "        size = []\n",
    "        res = 1\n",
    "        a = 1\n",
    "        for i in range(n):\n",
    "            size.append([[0, 0]] * n)\n",
    "        for i in range(n):\n",
    "            judge.append([False] * n)\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1 and not judge[i][j]:\n",
    "                    judge[i][j] = True\n",
    "                    count = 1\n",
    "                    pre = []\n",
    "                    queue = [[i, j]]\n",
    "                    while len(queue) != 0:\n",
    "                        temp = queue.pop(0)\n",
    "                        pre.append(temp)\n",
    "                        y, x = temp[0], temp[1]\n",
    "                        if x + 1 < n:\n",
    "                            if grid[y][x + 1] == 1 and not judge[y][x + 1]:\n",
    "                                judge[y][x + 1] = True\n",
    "                                queue.append([y, x + 1])\n",
    "                                count += 1\n",
    "                        if x - 1 >= 0:\n",
    "                            if grid[y][x - 1] == 1 and not judge[y][x - 1]:\n",
    "                                judge[y][x - 1] = True\n",
    "                                queue.append([y, x - 1])\n",
    "                                count += 1\n",
    "                        if y + 1 < n:\n",
    "                            if grid[y + 1][x] == 1 and not judge[y + 1][x]:\n",
    "                                judge[y + 1][x] = True\n",
    "                                queue.append([y + 1, x])\n",
    "                                count += 1\n",
    "                        if y - 1 >= 0:\n",
    "                            if grid[y - 1][x] == 1 and not judge[y - 1][x]:\n",
    "                                judge[y - 1][x] = True\n",
    "                                queue.append([y - 1, x])\n",
    "                                count += 1\n",
    "                    res = max(res, count)\n",
    "                    for item in pre:\n",
    "                        size[item[0]][item[1]] = [count, a]\n",
    "                    a += 1\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if size[i][j][0] == 0:\n",
    "                    temp_1, temp_2, temp_3, temp_4 = 0, 0, 0, 0\n",
    "                    b = [0] * 4\n",
    "                    if j + 1 < n:\n",
    "                        temp_1 = size[i][j + 1][0]\n",
    "                        b[0] = size[i][j + 1][1]\n",
    "                    if j - 1 >= 0:\n",
    "                        temp_2 = size[i][j - 1][0]\n",
    "                        if size[i][j - 1][0] != 0 and size[i][j - 1][1] in b:\n",
    "                            temp_2 = 0\n",
    "                        else:\n",
    "                            b[1] = size[i][j - 1][1]\n",
    "                    if i + 1 < n:\n",
    "                        temp_3 = size[i + 1][j][0]\n",
    "                        if size[i + 1][j][0] != 0 and size[i + 1][j][1] in b:\n",
    "                            temp_3 = 0\n",
    "                        else:\n",
    "                            b[2] = size[i + 1][j][1]\n",
    "                    if i - 1 >= 0:\n",
    "                        temp_4 = size[i - 1][j][0]\n",
    "                        if size[i - 1][j][0] != 0 and size[i - 1][j][1] in b:\n",
    "                            temp_4 = 0\n",
    "                        else:\n",
    "                            b[3] = size[i - 1][j][1]\n",
    "\n",
    "                    res = max(res, 1 + temp_1 + temp_2 + temp_3 + temp_4)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestIsland(self, grid: List[List[int]]) -> int:\n",
    "        \"\"\"\n",
    "        通过并查集来维护所有连通块的大小,并通过sz[idx]记录每个连通块的大小 idx是通过下标计算而来\n",
    "        例如i行j列 idx=i*n+j\n",
    "        然后遍历grid 找到0 然后根据四周连通块情况确定翻转\n",
    "        细节：编号从1开始 \n",
    "        \"\"\"\n",
    "        n = len(grid)\n",
    "        rs = 0\n",
    "        dirs = [[1,0],[-1,0],[0,1],[0,-1]]\n",
    "        p, sz = [i for i in range(n * n + 10)], [1 for _ in range(n * n + 10)] # sz是连通块的大小 p是并查集中每个点的祖先\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if grid[i][j]!=0:\n",
    "                    for dx,dy in dirs:\n",
    "                        x,y = i+dx,j+dy\n",
    "                        if 0<=x<n and 0<=y<n and grid[x][y]==1:\n",
    "                            self.union(p,sz,i*n+j+1,x*n+y+1)\n",
    "        \n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if grid[i][j]==1:\n",
    "                    rs = max(rs,sz[self.find(p,i*n+j+1)])\n",
    "                else:\n",
    "                    newArea = 1\n",
    "                    seen = set()\n",
    "                    for dx,dy in dirs:\n",
    "                        x,y = i+dx,j+dy\n",
    "                        if 0<=x<n and 0<=y<n and grid[x][y]==1:\n",
    "                            root = self.find(p,x*n+y+1)\n",
    "                            if root not in seen:#相同的不要重复计算\n",
    "                                seen.add(root)\n",
    "                                newArea += sz[root]\n",
    "                    rs = max(rs,newArea)\n",
    "        return rs\n",
    "                            \n",
    "\n",
    "    \n",
    "    def find(self,p,x):\n",
    "        if p[x]!=x:\n",
    "            p[x] = self.find(p,p[x])\n",
    "        return p[x]\n",
    "\n",
    "    def union(self,p,sz,a,b):\n",
    "        ra,rb = self.find(p,a),self.find(p,b)\n",
    "        if ra!=rb:#不是同一个祖先 需合并\n",
    "            if sz[ra]>sz[rb]: #方便统一操作\n",
    "                ra,rb = rb,ra\n",
    "            sz[rb] += sz[ra] #大的吞并小的\n",
    "            p[ra] = p[rb]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestIsland(self, grid: List[List[int]]) -> int:\n",
    "        def dfs(i, j):\n",
    "            p[i][j] = root\n",
    "            cnt[root] += 1\n",
    "            for a, b in [[0, -1], [0, 1], [-1, 0], [1, 0]]:\n",
    "                x, y = i + a, j + b\n",
    "                if 0 <= x < n and 0 <= y < n and grid[x][y] and p[x][y] == 0:\n",
    "                    dfs(x, y)\n",
    "\n",
    "        n = len(grid)\n",
    "        cnt = Counter()\n",
    "        p = [[0] * n for _ in range(n)]\n",
    "        root = 0\n",
    "        for i, row in enumerate(grid):\n",
    "            for j, v in enumerate(row):\n",
    "                if v and p[i][j] == 0:\n",
    "                    root += 1\n",
    "                    dfs(i, j)\n",
    "\n",
    "        ans = max(cnt.values(), default=0)\n",
    "        for i, row in enumerate(grid):\n",
    "            for j, v in enumerate(row):\n",
    "                if v == 0:\n",
    "                    t = 1\n",
    "                    vis = set()\n",
    "                    for a, b in [[0, -1], [0, 1], [-1, 0], [1, 0]]:\n",
    "                        x, y = i + a, j + b\n",
    "                        if 0 <= x < n and 0 <= y < n:\n",
    "                            root = p[x][y]\n",
    "                            if root not in vis:\n",
    "                                vis.add(root)\n",
    "                                t += cnt[root]\n",
    "                    ans = max(ans, t)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestIsland(self, grid: List[List[int]]) -> int:\n",
    "        n = len(grid)\n",
    "        tag = [[0] * n for _ in range(n)]\n",
    "        area = Counter()\n",
    "        def dfs(i: int, j: int) -> None:\n",
    "            tag[i][j] = t\n",
    "            area[t] += 1\n",
    "            for x, y in (i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1):  # 四个方向\n",
    "                if 0 <= x < n and 0 <= y < n and grid[x][y] and tag[x][y] == 0:\n",
    "                    dfs(x, y)\n",
    "        for i, row in enumerate(grid):\n",
    "            for j, x in enumerate(row):\n",
    "                if x and tag[i][j] == 0:  # 枚举没有访问过的陆地\n",
    "                    t = i * n + j + 1\n",
    "                    dfs(i, j)\n",
    "        ans = max(area.values(), default=0)\n",
    "\n",
    "        for i, row in enumerate(grid):\n",
    "            for j, x in enumerate(row):\n",
    "                if x == 0:  # 枚举可以添加陆地的位置\n",
    "                    new_area = 1\n",
    "                    connected = {0}\n",
    "                    for x, y in (i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1):  # 四个方向\n",
    "                        if 0 <= x < n and 0 <= y < n and tag[x][y] not in connected:\n",
    "                            new_area += area[tag[x][y]]\n",
    "                            connected.add(tag[x][y])\n",
    "                    ans = max(ans, new_area)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self, size):\n",
    "        self.parent = list(range(size))\n",
    "        self.rank = [0] * size\n",
    "        self.size = [1] * size\n",
    "\n",
    "    def find(self, x):\n",
    "        if self.parent[x] != x:\n",
    "            self.parent[x] = self.find(self.parent[x])\n",
    "        return self.parent[x]\n",
    "\n",
    "    def union(self, x, y):\n",
    "        rootX = self.find(x)\n",
    "        rootY = self.find(y)\n",
    "        if rootX != rootY:\n",
    "            if self.rank[rootX] > self.rank[rootY]:\n",
    "                self.parent[rootY] = rootX\n",
    "                self.size[rootX] += self.size[rootY]\n",
    "            elif self.rank[rootX] < self.rank[rootY]:\n",
    "                self.parent[rootX] = rootY\n",
    "                self.size[rootY] += self.size[rootX]\n",
    "            else:\n",
    "                self.parent[rootY] = rootX\n",
    "                self.size[rootX] += self.size[rootY]\n",
    "                self.rank[rootX] += 1\n",
    "\n",
    "    def getSize(self, x):\n",
    "        return self.size[self.find(x)]\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def largestIsland(self, grid: List[List[int]]) -> int:\n",
    "        n = len(grid)\n",
    "        uf = UnionFind(n * n)\n",
    "\n",
    "        def getIndex(x, y):\n",
    "            return x * n + y\n",
    "\n",
    "        directions = [(1, 0), (0, 1), (-1, 0), (0, -1)]\n",
    "\n",
    "        # Step 1: Union operation for all 1s\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1:\n",
    "                    for dx, dy in directions:\n",
    "                        ni, nj = i + dx, j + dy\n",
    "                        if 0 <= ni < n and 0 <= nj < n and grid[ni][nj] == 1:\n",
    "                            uf.union(getIndex(i, j), getIndex(ni, nj))\n",
    "\n",
    "        # Step 2: Find the largest island or set default to 0\n",
    "        res = max((uf.getSize(getIndex(i, j)) for i in range(n) for j in range(n) if grid[i][j] == 1), default=0)\n",
    "\n",
    "        # Step 3: Check every 0 and calculate the possible largest island\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 0:\n",
    "                    seen = set()\n",
    "                    for dx, dy in directions:\n",
    "                        ni, nj = i + dx, j + dy\n",
    "                        if 0 <= ni < n and 0 <= nj < n and grid[ni][nj] == 1:\n",
    "                            seen.add(uf.find(getIndex(ni, nj)))\n",
    "                    res = max(res, 1 + sum(uf.getSize(index) for index in seen))\n",
    "\n",
    "        return res if res != 0 else 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestIsland(self, grid: List[List[int]]) -> int:\n",
    "        m=len(grid)\n",
    "        n=len(grid[0])\n",
    "        mark=1\n",
    "        arr=[]\n",
    "        f=0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j]==1:\n",
    "                    mark+=1\n",
    "                    grid[i][j]=mark\n",
    "                    vis=[]\n",
    "                    stack=collections.deque()\n",
    "                    stack.append([i,j])\n",
    "                    while stack:\n",
    "                        x,y=stack.popleft()\n",
    "                        vis.append([x,y])\n",
    "                        for x1,y1 in [[x,y+1],[x,y-1],[x+1,y],[x-1,y]]:\n",
    "                            if 0<=x1<m and 0<=y1<n and grid[x1][y1]==1:\n",
    "                                grid[x1][y1]=mark\n",
    "                                stack.append([x1,y1])\n",
    "                    arr.append(vis)\n",
    "                elif grid[i][j]==0:\n",
    "                    f=1\n",
    "        if not arr:\n",
    "            return 1\n",
    "        mx=max([len(x) for x in arr])\n",
    "        if f==0:\n",
    "            return mx\n",
    "        size=collections.Counter()\n",
    "        for a in arr:\n",
    "            x,y=a[0]\n",
    "            size[grid[x][y]]=len(a)\n",
    "        print(mx)\n",
    "        for x in range(m):\n",
    "            for y in range(n):\n",
    "                 if grid[x][y]==0:\n",
    "                    tmp=1\n",
    "                    vis=set()\n",
    "                    for x1,y1 in [[x,y+1],[x,y-1],[x+1,y],[x-1,y]]:\n",
    "                        if 0<=x1<m and 0<=y1<n and grid[x1][y1]!=0 and grid[x1][y1] not in vis:\n",
    "                            tmp+=size[grid[x1][y1]]\n",
    "                            vis.add(grid[x1][y1])\n",
    "\n",
    "                    mx=max(tmp,mx)\n",
    "\n",
    "        return mx\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestIsland(self, grid: List[List[int]]) -> int:\n",
    "        m=len(grid)\n",
    "        n=len(grid[0])\n",
    "        mark=1\n",
    "        arr=[]\n",
    "        f=0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j]==1:\n",
    "                    mark+=1\n",
    "                    grid[i][j]=mark\n",
    "                    vis=[]\n",
    "                    stack=collections.deque()\n",
    "                    stack.append([i,j])\n",
    "                    while stack:\n",
    "                        x,y=stack.popleft()\n",
    "                        vis.append([x,y])\n",
    "                        for x1,y1 in [[x,y+1],[x,y-1],[x+1,y],[x-1,y]]:\n",
    "                            if 0<=x1<m and 0<=y1<n and grid[x1][y1]==1:\n",
    "                                grid[x1][y1]=mark\n",
    "                                stack.append([x1,y1])\n",
    "                    arr.append(vis)\n",
    "                elif grid[i][j]==0:\n",
    "                    f=1\n",
    "        if not arr:\n",
    "            return 1\n",
    "        mx=max([len(x) for x in arr])\n",
    "        if f==0:\n",
    "            return mx\n",
    "        size=collections.Counter()\n",
    "        for a in arr:\n",
    "            x,y=a[0]\n",
    "            size[grid[x][y]]=len(a)\n",
    "        #print(mx)\n",
    "        for x in range(m):\n",
    "            for y in range(n):\n",
    "                 if grid[x][y]==0:\n",
    "                    tmp=1\n",
    "                    vis=set()\n",
    "                    for x1,y1 in [[x,y+1],[x,y-1],[x+1,y],[x-1,y]]:\n",
    "                        if 0<=x1<m and 0<=y1<n and grid[x1][y1]!=0 and grid[x1][y1] not in vis:\n",
    "                            tmp+=size[grid[x1][y1]]\n",
    "                            vis.add(grid[x1][y1])\n",
    "\n",
    "                    mx=max(tmp,mx)\n",
    "\n",
    "        return mx\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestIsland(self, grid: List[List[int]]) -> int:\n",
    "        N = len(grid)\n",
    "        islands = [[-1] * N for _ in range(N)]\n",
    "        areas = Counter()\n",
    "        tag = 0\n",
    "        delta = [(1, 0), (-1, 0), (0, 1), (0, -1)]\n",
    "\n",
    "        def dfs(i, j):\n",
    "            if islands[i][j] != -1: return\n",
    "            if not grid[i][j]: return\n",
    "            islands[i][j] = tag\n",
    "            areas[tag] += 1\n",
    "            for x, y in delta:\n",
    "                _i, _j = i + x, j + y\n",
    "                if _i < 0 or _i >= N or _j < 0 or _j >= N: continue\n",
    "                dfs(_i, _j)\n",
    "\n",
    "        for i in range(N):\n",
    "            for j in range(N):\n",
    "                dfs(i, j)\n",
    "                tag += 1\n",
    "\n",
    "        R = max(areas.values(), default=0)\n",
    "\n",
    "        for i in range(N):\n",
    "            for j in range(N):\n",
    "                if grid[i][j]: continue\n",
    "                area = 1\n",
    "                joint = set()\n",
    "                for x, y in delta:\n",
    "                    _i, _j = i + x, j + y\n",
    "                    if _i < 0 or _i >= N or _j < 0 or _j >= N: continue\n",
    "                    tag = islands[_i][_j]\n",
    "                    if tag in joint: continue\n",
    "                    joint.add(tag)\n",
    "                    area += areas[tag]\n",
    "                R = max(R, area)\n",
    "                    \n",
    "        return R"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestIsland(self, grid: List[List[int]]) -> int:\n",
    "        dxs = [0, 0, 1, -1]\n",
    "        dys = [1, -1, 0, 0]\n",
    "\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        cur_tag = 0\n",
    "        tag = [[-1 for _ in range(n)] for _ in range(m)] \n",
    "        \n",
    "        cur_size = 0\n",
    "        size = []\n",
    "        def dfs(x, y):\n",
    "            nonlocal cur_size, size, tag, cur_tag\n",
    "            cur_size += 1\n",
    "            tag[x][y] = cur_tag\n",
    "\n",
    "            for dx, dy in zip(dxs, dys):\n",
    "                new_x, new_y = x + dx, y + dy\n",
    "                if new_x >= 0 and new_x < m and new_y >= 0 and new_y < n and grid[new_x][new_y] and tag[new_x][new_y] == -1:\n",
    "                    dfs(new_x, new_y)\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] and tag[i][j] == -1:\n",
    "                    cur_size = 0\n",
    "                    dfs(i, j)\n",
    "                    cur_tag += 1\n",
    "                    size.append(cur_size)\n",
    "\n",
    "        max_size = max(size, default=0)\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 0:\n",
    "                    new_size = 1\n",
    "                    visited = []\n",
    "                    for dx, dy in zip(dxs, dys):\n",
    "                        new_x, new_y = i + dx, j + dy\n",
    "                        if new_x >= 0 and new_x < m and new_y >= 0 and new_y < n and tag[new_x][new_y] != -1 and tag[new_x][new_y] not in visited:\n",
    "                            new_size += size[tag[new_x][new_y]]\n",
    "                            visited.append(tag[new_x][new_y])\n",
    "                    max_size = max(max_size, new_size)\n",
    "        return max_size"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestIsland(self, grid: List[List[int]]) -> int:\n",
    "\n",
    "        tags = [[-1, -1] * len(grid[0]) for _ in range(len(grid))]\n",
    "\n",
    "        self.size = 0\n",
    "        self.cur_island = []\n",
    "        self.island_id = 0\n",
    "\n",
    "        def dfs(row, col):\n",
    "            if not 0 <= row < len(grid) or not 0 <= col < len(grid[0]):\n",
    "                return\n",
    "            if grid[row][col] == 0 or grid[row][col] == 2:\n",
    "                return\n",
    "            grid[row][col] = 2\n",
    "            self.size += 1\n",
    "            self.cur_island.append([row, col])\n",
    "            dfs(row-1, col)\n",
    "            dfs(row+1, col)\n",
    "            dfs(row, col-1)\n",
    "            dfs(row, col+1)\n",
    "        \n",
    "        ans = 0\n",
    "        for row in range(len(grid)):\n",
    "            for col in range(len(grid[0])):\n",
    "                if grid[row][col] == 1:\n",
    "                    self.size = 0\n",
    "                    self.cur_island = []\n",
    "                    dfs(row, col)\n",
    "                    ans = max(ans, self.size)\n",
    "                    for a, b in self.cur_island:\n",
    "                        tags[a][b] = [self.island_id, self.size]\n",
    "                    self.island_id += 1\n",
    "        \n",
    "        if self.island_id == 1:\n",
    "            if ans == len(grid) * len(grid[0]):\n",
    "                return ans\n",
    "            else:\n",
    "                return ans + 1\n",
    "        \n",
    "        if self.island_id == 0:\n",
    "            return 1\n",
    "\n",
    "        diff = [[0, 1], [0, -1], [1, 0], [-1, 0]]\n",
    "        for row in range(len(grid)):\n",
    "            for col in range(len(grid[0])):\n",
    "                if grid[row][col] == 0:\n",
    "                    new_size = 0\n",
    "                    next_islands_id = []\n",
    "                    for dx, dy in diff:\n",
    "                        drow, dcol = row + dx, col + dy\n",
    "                        if 0 <= drow < len(grid) and 0 <= dcol < len(grid[0]) and grid[drow][dcol] != 0:\n",
    "                            id, size = tags[drow][dcol]\n",
    "                            if not id in next_islands_id:\n",
    "                                next_islands_id.append(id)\n",
    "                                new_size += size\n",
    "                    ans = max(ans, new_size + 1)\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestIsland(self, grid: List[List[int]]) -> int:\n",
    "        N = len(grid)\n",
    "        vis = [[False for _ in range(N)] for _ in range(N)]\n",
    "        def is_valid(r, c):\n",
    "            return r >= 0 and r < N and c >= 0 and c < N\n",
    "        islands = [[None for _ in range(N)] for _ in range(N)]\n",
    "        areas = []\n",
    "        def dfs(r, c, i) -> int:\n",
    "            if not is_valid(r, c) or vis[r][c]:\n",
    "                return 0\n",
    "            vis[r][c] = True\n",
    "            if grid[r][c] != 1:\n",
    "                return 0\n",
    "            islands[r][c] = i\n",
    "            ans = 1\n",
    "            for rn, cn in [(r-1, c), (r+1, c), (r, c-1), (r, c+1)]:\n",
    "                ans += dfs(rn, cn, i)\n",
    "            return ans\n",
    "        ans = 0\n",
    "        i = 0\n",
    "        for r in range(N):\n",
    "            for c in range(N):\n",
    "                if not vis[r][c] and grid[r][c] == 1:\n",
    "                    area = dfs(r, c, i)\n",
    "                    ans = max(ans, area)\n",
    "                    areas.append(area)\n",
    "                    i += 1\n",
    "        for r in range(N):\n",
    "            for c in range(N):\n",
    "                if grid[r][c] == 0:\n",
    "                    ids = set()\n",
    "                    for rn, cn in [(r-1, c), (r+1, c), (r, c-1), (r, c+1)]:\n",
    "                        if is_valid(rn, cn) and grid[rn][cn] == 1:\n",
    "                            ids.add(islands[rn][cn])\n",
    "                    area = 1\n",
    "                    for i in ids:\n",
    "                        area += areas[i]\n",
    "                    ans = max(ans, area)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestIsland(self, grid: List[List[int]]) -> int:\n",
    "        row = len(grid)\n",
    "        col = len(grid[0])\n",
    "        extra = row*col\n",
    "\n",
    "        for i in range(row):\n",
    "            for j in range(col):\n",
    "                if grid[i][j] == 1:\n",
    "                    que = deque()\n",
    "                    pos = []\n",
    "                    que.append((i, j))\n",
    "                    pos.append((i, j))\n",
    "                    grid[i][j] = 0\n",
    "                    area = 1\n",
    "                    while que:\n",
    "                       r, c = que.popleft()\n",
    "                       for x, y in [(r - 1, c), (r, c + 1), (r + 1, c), (r, c - 1)]:\n",
    "                            if 0 <= x < row and 0 <= y < col and grid[x][y] == 1:\n",
    "                                que.append((x, y))\n",
    "                                pos.append((x, y))\n",
    "                                area += 1\n",
    "                                grid[x][y] = 0\n",
    "                    area += extra\n",
    "                    extra *= 2      \n",
    "                    for x, y in pos:\n",
    "                        grid[x][y] = area\n",
    "\n",
    "        cur_max = -1\n",
    "        for i in range(row):\n",
    "            for j in range(col):\n",
    "                if grid[i][j] == 0:\n",
    "                    exist = set()\n",
    "                    this_max = 1\n",
    "                    for x, y in [(i - 1, j), (i, j + 1), (i+ 1, j), (i, j - 1)]:\n",
    "                        if 0 <= x < row and 0 <= y < col:\n",
    "                            val = grid[x][y]\n",
    "                            if val not in exist: \n",
    "                                this_max += val%(row*col)\n",
    "                                exist.add(val)\n",
    "                    cur_max = max(cur_max, this_max)\n",
    "\n",
    "\n",
    "        return cur_max if cur_max != -1 else row*col"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestIsland(self, grid: List[List[int]]) -> int:\n",
    "\n",
    "        def dfs(v, ccid):\n",
    "            x, y = v[0], v[1]\n",
    "            visited[x][y] = ccid\n",
    "            for dx, dy in Direct:\n",
    "                next_x, next_y = x + dx, y + dy\n",
    "                if 0 <= next_x < m and 0 <= next_y < n \\\n",
    "                        and visited[next_x][next_y] == -1 \\\n",
    "                        and grid[next_x][next_y] == 1:\n",
    "                    w = (next_x, next_y)\n",
    "                    dfs(w, ccid)\n",
    "\n",
    "        def bfs(s, ccid):\n",
    "            q = deque()\n",
    "            q.append(s)\n",
    "            visited[s[0]][s[1]] = ccid\n",
    "            while q:\n",
    "                v = q.popleft()\n",
    "                x, y = v[0], v[1]\n",
    "                for dx, dy in Direct:\n",
    "                    next_x, next_y = x + dx, y + dy\n",
    "                    if 0 <= next_x < m and 0 <= next_y < n \\\n",
    "                            and visited[next_x][next_y] == -1 \\\n",
    "                            and grid[next_x][next_y] == 1:\n",
    "                        w = (next_x, next_y)\n",
    "                        q.append(w)\n",
    "                        visited[next_x][next_y] = ccid\n",
    "\n",
    "        def groups():\n",
    "            res = [[] for _ in range(ccount)]\n",
    "            for x in range(m):\n",
    "                for y in range(n):\n",
    "                    if grid[x][y] == 1:\n",
    "                        res[visited[x][y]].append((x, y))\n",
    "            return res\n",
    "\n",
    "        def border_group(v):\n",
    "            x, y = v[0], v[1]\n",
    "            sum_area = 0\n",
    "            group_ids = set()\n",
    "            for dx, dy in Direct:\n",
    "                next_x, next_y = x + dx, y + dy\n",
    "                if 0 <= next_x < m and 0 <= next_y < n and grid[next_x][next_y] == 1:\n",
    "                    group_ids.add(visited[next_x][next_y])\n",
    "            for ccid in group_ids:\n",
    "                sum_area += len(groups_[ccid])\n",
    "            return sum_area + 1\n",
    "\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        visited = [[-1] * n for _ in range(m)]\n",
    "        Direct = [(0, 1), (0, -1), (1, 0), (-1, 0)]\n",
    "        ccount = 0\n",
    "        for x in range(m):\n",
    "            for y in range(n):\n",
    "                if 0 <= x < m and 0 <= y < n and visited[x][y] == -1 and grid[x][y] == 1:\n",
    "                    # dfs((x, y), ccount)\n",
    "                    bfs((x, y), ccount)\n",
    "                    ccount += 1\n",
    "        groups_ = groups()\n",
    "        max_area = 0\n",
    "        for x in range(m):\n",
    "            for y in range(n):\n",
    "                if 0 <= x < m and 0 <= y < n and grid[x][y] == 0:\n",
    "                    max_area = max(max_area, border_group((x, y)))\n",
    "        if max_area != 0:\n",
    "            return max_area\n",
    "        else:\n",
    "            return max(len(gp) for gp in groups_)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    from enum import Enum\n",
    "\n",
    "    class Move(Enum):\n",
    "        up = (-1, 0)\n",
    "        down = (1, 0)\n",
    "        left = (0, -1)\n",
    "        right = (0, 1)\n",
    "\n",
    "    def largestIsland(self, grid: List[List[int]]) -> int:\n",
    "        \"\"\"\n",
    "        At most one 0 is allowed to flipped to 1, return maximum island after the change\n",
    "\n",
    "            1) DFS/BFS on all grids with visited and return the area of each island\n",
    "\n",
    "            2) DFS/BFS will mark each island with an identifier\n",
    "\n",
    "            3) [identifier -> area of the island]\n",
    "\n",
    "            4) Simulate the flip and add the area of all its neighbors using mapping from 3)\n",
    "        \"\"\"\n",
    "        self.grid = grid\n",
    "\n",
    "        return max(self._largest_island(), self._largest_island_after_flip())\n",
    "\n",
    "    def _largest_island(self) -> int:\n",
    "        # DFS/BFS on all cells (step 1 -> 3)\n",
    "\n",
    "        m = len(self.grid)\n",
    "        n = len(self.grid[0])\n",
    "\n",
    "        self.visited = set()\n",
    "        self.identifier = 1\n",
    "        self.id2area = {}\n",
    "        max_area = 0\n",
    "\n",
    "        for y in range(m):\n",
    "            for x in range(n):\n",
    "                if (y, x) in self.visited:\n",
    "                    continue\n",
    "                if self.grid[y][x] == 0:\n",
    "                    continue\n",
    "\n",
    "                # area = self._dfs(y, x)\n",
    "                area = self._bfs(y, x)\n",
    "\n",
    "                max_area = max(max_area, area)\n",
    "\n",
    "                self.id2area[self.identifier] = area\n",
    "                self.identifier += 1\n",
    "\n",
    "        return max_area\n",
    "\n",
    "    def _largest_island_after_flip(self) -> int:\n",
    "        # Simulate the flip on all 0s cells (step 4)\n",
    "\n",
    "        m = len(self.grid)\n",
    "        n = len(self.grid[0])\n",
    "        max_area = 0\n",
    "\n",
    "        for y in range(m):\n",
    "            for x in range(n):\n",
    "                if self.grid[y][x] != 0:\n",
    "                    continue\n",
    "\n",
    "                area = 1\n",
    "                visited = set()\n",
    "                # Add up neighbors\n",
    "                for move in self.Move:\n",
    "                    y_dir, x_dir = move.value\n",
    "                    next_y, next_x = y + y_dir, x + x_dir\n",
    "\n",
    "                    if self._oob(next_y, next_x):\n",
    "                        continue\n",
    "\n",
    "                    # Skip duplicates\n",
    "                    _id = self.grid[next_y][next_x]\n",
    "                    if _id in visited:\n",
    "                        continue\n",
    "\n",
    "                    area += self.id2area.get(_id, 0)\n",
    "                    visited.add(_id)\n",
    "\n",
    "                max_area = max(max_area, area)\n",
    "\n",
    "        return max_area\n",
    "\n",
    "    def _dfs(self, y: int, x: int) -> int:\n",
    "        if (y, x) in self.visited:\n",
    "            return 0\n",
    "        if self._oob(y, x):\n",
    "            return 0\n",
    "        if self.grid[y][x] == 0:\n",
    "            return 0\n",
    "\n",
    "        self.visited.add((y, x))\n",
    "        self.grid[y][x] = self.identifier\n",
    "\n",
    "        area = 1\n",
    "        for move in self.Move:\n",
    "            y_dir, x_dir = move.value\n",
    "            area += self._dfs(y + y_dir, x + x_dir)\n",
    "\n",
    "        return area\n",
    "\n",
    "    def _bfs(self, y: int, x: int) -> int:\n",
    "        from collections import deque\n",
    "\n",
    "        queue = deque([(y, x)])\n",
    "        self.visited.add((y, x))\n",
    "        area = 0\n",
    "\n",
    "        while queue:\n",
    "            cur_y, cur_x = queue.popleft()\n",
    "            self.grid[cur_y][cur_x] = self.identifier\n",
    "            area += 1\n",
    "\n",
    "            for move in self.Move:\n",
    "                y_dir, x_dir = move.value\n",
    "                next_y, next_x = cur_y + y_dir, cur_x + x_dir\n",
    "\n",
    "                if (next_y, next_x) in self.visited:\n",
    "                    continue\n",
    "                if self._oob(next_y, next_x):\n",
    "                    continue\n",
    "                if self.grid[next_y][next_x] == 0:\n",
    "                    continue\n",
    "\n",
    "                queue.append((next_y, next_x))\n",
    "                self.visited.add((next_y, next_x))\n",
    "\n",
    "        return area\n",
    "\n",
    "    def _oob(self, y: int, x: int) -> bool:\n",
    "        m = len(self.grid)\n",
    "        n = len(self.grid[0])\n",
    "        v_oob = (y < 0 or y >= m)\n",
    "        h_oob = (x < 0 or x >= n)\n",
    "\n",
    "        return v_oob or h_oob\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestIsland(self, grid: List[List[int]]) -> int:\n",
    "        # 修改 grid 标记岛\n",
    "        # 修改 can_go 标记 visited\n",
    "        island_size_map = {}\n",
    "        n,m = len(grid),len(grid[0])\n",
    "        can_go = [[False if grid[i][j] == 0 else True for j in range(m)] for i in range(n)]\n",
    "\n",
    "        def is_valid(pos):\n",
    "            if pos[0] >= 0 and pos[0] < n and pos[1] >= 0 and pos[1] < m and can_go[pos[0]][pos[1]] is True:\n",
    "                return True\n",
    "            return False\n",
    "\n",
    "        def get_neighbour(pos):\n",
    "            res = []\n",
    "            candidates = [[pos[0]-1,pos[1]],[pos[0]+1,pos[1]],[pos[0],pos[1]-1],[pos[0],pos[1]+1]]\n",
    "            for i in candidates:\n",
    "                if is_valid(i):\n",
    "                    res.append(i)\n",
    "            return res\n",
    "        \n",
    "        def dfs(pos,island):\n",
    "            if is_valid(pos):\n",
    "                grid[pos[0]][pos[1]] = island\n",
    "                nonlocal size\n",
    "                size += 1\n",
    "                can_go[pos[0]][pos[1]] = False\n",
    "                neighbours = get_neighbour(pos)\n",
    "                for n in neighbours:\n",
    "                    dfs(n,island)\n",
    "\n",
    "        cur_island = 1\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                size = 0\n",
    "                dfs([i,j],cur_island)\n",
    "                if size != 0:\n",
    "                    island_size_map[cur_island] = size\n",
    "                    cur_island += 1\n",
    "        # print(grid)\n",
    "        if island_size_map == {}:\n",
    "            return 1\n",
    "        can_go = [[True for j in range(m)] for i in range(n)]\n",
    "        max_size = max(island_size_map.values())\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if grid[i][j] == 0:\n",
    "                    neighbours = get_neighbour([i,j])\n",
    "                    neighbour_island = list(set([grid[n[0]][n[1]] for n in neighbours if grid[n[0]][n[1]] != 0]))\n",
    "                    cur_union_size = 0\n",
    "                    for k in neighbour_island:\n",
    "                        cur_union_size += island_size_map[k]\n",
    "                    max_size = max(max_size,cur_union_size+1)\n",
    "            \n",
    "        return max_size"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestIsland(self, grid: List[List[int]]) -> int:\n",
    "        self.m , self.n = len(grid), len(grid[0])\n",
    "        if self.m==0 or self.n==0:\n",
    "            return 0\n",
    "        \n",
    "        self.list1 = []\n",
    "        self.list2 = []\n",
    "        def basecase(i,j):\n",
    "            if i>=0 and i<self.m and j>=0 and j<self.n:\n",
    "                return True\n",
    "            return False\n",
    "\n",
    "        def dfs(grid, i,j):## postlist保存位置\n",
    "            ## 标记每个岛屿的面积和位置\n",
    "            if not basecase(i,j):\n",
    "                return 0, []\n",
    "            if grid[i][j]!=1:\n",
    "                return 0, []\n",
    "            grid[i][j]=2\n",
    "            left, pos1 = dfs(grid, i, j-1)\n",
    "            right, pos2 = dfs(grid, i,j+1)\n",
    "            top, pos3 = dfs(grid, i-1, j)\n",
    "            bottom, pos4 = dfs(grid, i+1, j)\n",
    "            return 1+left+right+top+bottom,   [(i,j)]+pos1+pos2+pos3+pos4\n",
    "        \n",
    "        ##第一次循环\n",
    "        for i in range(self.m):\n",
    "            for j in range(self.n):\n",
    "                cura, curlist = dfs(grid, i,j)\n",
    "                if cura>0:\n",
    "                    self.list1.append(cura)\n",
    "                    self.list2.append(curlist)\n",
    "        \n",
    "        ## \n",
    "        grida = [[-1]*self.n for _ in range(self.m)]\n",
    "        # 第几个小岛 index表示第几个小岛\n",
    "        for i in range(len(self.list2)):\n",
    "            for c in self.list2[i]:\n",
    "                grida[c[0]][c[1]] = i ##i\n",
    "        if not self.list1:\n",
    "            return 1\n",
    "\n",
    "        self.res = max(self.list1)\n",
    "        def dfs2(grid,i,j):\n",
    "            if not basecase(i,j):\n",
    "                return -1 ##边界\n",
    "            if grid[i][j]!=-1: ##小岛\n",
    "                return grid[i][j] ## 返回 \n",
    "            \n",
    "\n",
    "            grid[i][j]=-2\n",
    "            left = dfs2(grid, i,j-1)\n",
    "            right = dfs2(grid, i,j+1)\n",
    "            top = dfs2(grid, i-1, j)\n",
    "            bottm = dfs2(grid, i+1, j)\n",
    "            #area = [left[0], right[0], top[0], bottm[0]]\n",
    "            index = [left, right, top, bottm]\n",
    "            #1 去除相同元素index里面的\n",
    "            index = list(set(index))\n",
    "            ##eg index=[-1, 0,2]\n",
    "             ##\n",
    "            if index:\n",
    "                index = [c for c in index if c>=0]\n",
    "                self.res = max(self.res, 1+sum([self.list1[ii] for ii in index]))\n",
    "            return grid[i][j]\n",
    "        for i in range(self.m):\n",
    "            for j in range(self.n):\n",
    "                dfs2(grida, i,j)\n",
    "        return self.res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestIsland(self, grid: List[List[int]]) -> int:\n",
    "        maxArea=0\n",
    "        m,n=len(grid),len(grid[0])\n",
    "        gird_a=copy.deepcopy(grid)\n",
    "        def dfs(x,y,index):\n",
    "            if x<0 or x>=m or y<0 or y>=n or grid[x][y]!=1:\n",
    "                return 0\n",
    "            grid[x][y]=index#标记已经访问\n",
    "            return dfs(x+1,y,index)+dfs(x-1,y,index)+dfs(x,y+1,index)+dfs(x,y-1,index)+1\n",
    "\n",
    "        def setArea(x,y,area,index):\n",
    "            if x<0 or x>=m or y<0 or y>=n or grid[x][y]!=index:\n",
    "                return \n",
    "            gird_a[x][y]=area\n",
    "            grid[x][y]*=-1\n",
    "            setArea(x+1,y,area,index)\n",
    "            setArea(x-1,y,area,index)\n",
    "            setArea(x,y+1,area,index)\n",
    "            setArea(x,y-1,area,index)\n",
    "            return \n",
    "\n",
    "        island=2\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j]==1:\n",
    "                    areaIsland=dfs(i,j,island)\n",
    "                    setArea(i,j,areaIsland,island)\n",
    "                    island+=1\n",
    "        print(gird_a)\n",
    "\n",
    "        def dfsArea(x,y):\n",
    "            return gird_a[x][y]\n",
    "        def findAroundArea(x,y):\n",
    "            i_set=set()\n",
    "            area=1\n",
    "            if x>0 and grid[x-1][y] not in i_set and grid[x-1][y]!=0:\n",
    "                i_set.add(grid[x-1][y])\n",
    "                area+=dfsArea(x-1,y)\n",
    "            if x<m-1 and grid[x+1][y] not in i_set and grid[x+1][y]!=0:\n",
    "                i_set.add(grid[x+1][y])\n",
    "                area+=dfsArea(x+1,y)\n",
    "            if y>0 and grid[x][y-1] not in i_set and grid[x][y-1]!=0:\n",
    "                i_set.add(grid[x][y-1])\n",
    "                area+=dfsArea(x,y-1)\n",
    "            if y<n-1 and grid[x][y+1] not in i_set and grid[x][y+1]!=0:\n",
    "                i_set.add(grid[x][y+1])\n",
    "                area+=dfsArea(x,y+1)\n",
    "            return area\n",
    "        \n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j]==0:\n",
    "                    maxArea=max(maxArea,findAroundArea(i,j))\n",
    "        if maxArea==0:\n",
    "            return m*n\n",
    "        return maxArea"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestIsland(self, grid: List[List[int]]) -> int:\n",
    "        self.n = len(grid)\n",
    "        directions = [[0,1],[0,-1],[1,0],[-1,0]]\n",
    "        # 记录每个「点」的「岛屿标记」\n",
    "        gridTag = [[None] * self.n for _ in range(self.n)]\n",
    "        # hash map。记录每个岛屿的面积\n",
    "        tagToArea = collections.defaultdict(int)\n",
    "\n",
    "        def dfs(grid, r, c, tag, visited):\n",
    "            if r not in range(self.n) or c not in range(self.n): return\n",
    "            if (r,c) in visited: return\n",
    "            # 遇到海水就return，一次dfs只期望标记完一个岛屿\n",
    "            if grid[r][c] == 0: return \n",
    "            # 打标；算面积\n",
    "            if grid[r][c] == 1:\n",
    "                gridTag[r][c] = tag\n",
    "                tagToArea[tag] += 1\n",
    "            visited.add((r,c))\n",
    "            for dr,dc in directions:\n",
    "                dfs(grid, r+dr, c+dc, tag, visited)\n",
    "        \n",
    "        # 打标；算面积\n",
    "        visited = set()\n",
    "        for r in range(self.n):\n",
    "            for c in range(self.n):\n",
    "                if grid[r][c] == 1 and (r,c) not in visited:\n",
    "                    tag = r * self.n + c\n",
    "                    dfs(grid, r, c, tag, visited)\n",
    "        \n",
    "        # 找出所有 0，算出合并面积, 更新最大合并面积\n",
    "        res = 0\n",
    "        for r in range(self.n):\n",
    "            for c in range(self.n):\n",
    "                if grid[r][c] == 0:\n",
    "                    merge = 1\n",
    "                    # 防止 0 各方向的岛屿，其实是同一个岛屿\n",
    "                    visitedTag = set()\n",
    "                    for dr,dc in directions:\n",
    "                        nr, nc = r+dr, c+dc\n",
    "                        if nr in range(self.n) and nc in range(self.n) and grid[nr][nc] == 1:\n",
    "                            tag = gridTag[nr][nc]\n",
    "                            if tag not in visitedTag:\n",
    "                                merge += tagToArea[tag]\n",
    "                                visitedTag.add(tag)\n",
    "                    res = max(res, merge)\n",
    "\n",
    "        # edge case\n",
    "        if res == 0: return self.n ** 2\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestIsland(self, grid: List[List[int]]) -> int:\n",
    "        n = len(grid)\n",
    "        def bfs(i, j, grid, vis, edges):\n",
    "            que = deque()\n",
    "            que.append((i,j))\n",
    "            edge = set()\n",
    "            area = 1\n",
    "            while que:\n",
    "                i, j = que.popleft()\n",
    "                for x, y in (i+1,j),(i,j+1),(i-1,j),(i,j-1):\n",
    "                    if 0 <= x < n and 0 <= y < n and not vis[x][y]:\n",
    "                        if grid[x][y] == 1:\n",
    "                            area += 1\n",
    "                            que.append((x,y))\n",
    "                            vis[x][y] = True\n",
    "                        else:\n",
    "                            edge.add((x,y))\n",
    "            for x,y in edge:\n",
    "                if (x,y) in edges:\n",
    "                    edges[(x,y)] += area\n",
    "                else:\n",
    "                    edges[(x,y)] = area\n",
    "            return area\n",
    "        \n",
    "        vis = [[False for _ in range(n)] for _ in range(n)]\n",
    "        area_max = 0\n",
    "        edges = dict()\n",
    "        for i, row in enumerate(grid):\n",
    "            for j,col in enumerate(row):\n",
    "                if not vis[i][j] and col == 1:\n",
    "                    vis[i][j] = True\n",
    "                    area = bfs(i, j, grid, vis, edges)\n",
    "                    area_max = max(area, area_max)\n",
    "        if edges == {}:\n",
    "            return area_max if area_max != 0 else 1\n",
    "        else:\n",
    "            return max(edges.values()) + 1\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "def find_father(grid, i, j,dot_father,set_size,used,father):\n",
    "\n",
    "\n",
    "    if grid[i][j] == 0:\n",
    "        return\n",
    "\n",
    "    dot_father[(i, j)] = father\n",
    "    set_size[father] += 1\n",
    "    used.add((i, j))\n",
    "\n",
    "    if i-1>=0:\n",
    "        if (i-1,j) not in used:\n",
    "            used.add((i-1,j))\n",
    "            find_father(grid, i - 1, j, dot_father,set_size,used,father)\n",
    "\n",
    "    if len(grid)>i + 1 >= 0:\n",
    "        if (i+1,j) not in used:\n",
    "            used.add((i+1,j))\n",
    "            find_father(grid, i + 1, j, dot_father,set_size,used,father)\n",
    "\n",
    "\n",
    "    if len(grid[0]) > j+1 >=0:\n",
    "        if (i,j+1) not in used:\n",
    "            used.add((i,j+1))\n",
    "            find_father(grid,i,j+1,dot_father,set_size,used,father)\n",
    "\n",
    "\n",
    "    if len(grid[0])> j-1 >=0:\n",
    "        if (i,j-1) not in used:\n",
    "            used.add((i,j-1))\n",
    "            find_father(grid,i,j-1,dot_father,set_size,used,father)\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def largestIsland(self, grid: List[List[int]]) -> int:\n",
    "        dot_father = {}\n",
    "        set_size = collections.Counter()\n",
    "\n",
    "\n",
    "\n",
    "        for i in range(len(grid)):\n",
    "            for j in range(len(grid[0])):\n",
    "                if grid[i][j] == 1 and (i,j) not in dot_father:\n",
    "                    father = len(dot_father)+1\n",
    "                    find_father(grid,i,j,dot_father,set_size,set(),father)\n",
    "\n",
    "\n",
    "        res = list(dot_father.values())\n",
    "        res = collections.Counter(res)\n",
    "        res = max(res.values()) if res.__len__()>0 else 0\n",
    "        for i in range(len(grid)):\n",
    "            for j in range(len(grid[0])):\n",
    "                if grid[i][j] == 0:\n",
    "                    f1 = dot_father[(i-1,j)] if (i-1,j) in dot_father else -1\n",
    "                    f2 = dot_father[(i+1,j)] if (i+1,j) in dot_father else -1\n",
    "                    if f2==f1:\n",
    "                        f2 = -2\n",
    "                    f3 = dot_father[(i,j+1)] if (i,j+1) in dot_father else -1\n",
    "                    if f3==f1 or f3==f2:\n",
    "                        f3 = -2\n",
    "                    f4 = dot_father[(i, j - 1)] if (i, j - 1) in dot_father else -1\n",
    "                    if f4==f3 or f4==f2 or f4==f1:\n",
    "                        f4 = -2\n",
    "\n",
    "                    tem = 1\n",
    "                    if f1 not in [-1,-2]:\n",
    "                        tem += set_size[f1]\n",
    "                    if f2 not in [-1,-2]:\n",
    "                        tem += set_size[f2]\n",
    "                    if f3 not in [-1,-2]:\n",
    "                        tem += set_size[f3]\n",
    "                    if f4 not in [-1,-2]:\n",
    "                        tem += set_size[f4]\n",
    "\n",
    "                    res = max(res,tem)\n",
    "\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def largestIsland(self, grid):\n",
    "        \"\"\"\n",
    "        :type grid: List[List[int]]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        dirction = [(i,j) for i in [-1,0,1] for j in [-1,0,1] if abs(i)!=abs(j)]\n",
    "        tag = [[0]*n for i in range(m)]\n",
    "        count = {}\n",
    "        visited = [[False]*n for i in range(m)]\n",
    "        res = 0\n",
    "        def chack(i,j):\n",
    "            s = set()\n",
    "            for dirc in dirction:\n",
    "                x = i+dirc[0]\n",
    "                y = j + dirc[1]\n",
    "                if 0<=x<m and 0<=y<n and tag[x][y]!=0:\n",
    "                    s.add(tag[x][y])\n",
    "            return s\n",
    "        def dfs(i,j,visted,index):\n",
    "            res = 0\n",
    "            if not (0<=i<m and 0<=j<n and visted[i][j]==False and grid[i][j]==1):\n",
    "                return 0 \n",
    "            visited[i][j]=True\n",
    "            tag[i][j]=index\n",
    "            for dirc in dirction:\n",
    "                res +=dfs(i+dirc[0],j+dirc[1],visted,index)\n",
    "            return 1+res\n",
    "       \n",
    "            \n",
    "        index = 2\n",
    "        for row in range(m):\n",
    "            for col in range(n):\n",
    "                if grid[row][col]!=0 and visited[row][col]!=True:\n",
    "                    temp_res = dfs(row,col,visited,index)\n",
    "                    res = max(temp_res,res)\n",
    "                    count[index]=temp_res\n",
    "                    index+=1\n",
    "        for row in range(m):\n",
    "            for col in range(n):\n",
    "                if grid[row][col]==0:\n",
    "                    s = chack(row,col)\n",
    "                    current = 1\n",
    "                    for index in s:\n",
    "                        current+=count[index]\n",
    "                    res = max(res,current)\n",
    "                \n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "class Solution:\n",
    "    def DFS(self,grid,x,y,m,n,island_tag):\n",
    "\n",
    "        if 0<=x<=m-1 and 0<=y<=n-1 and grid[x,y]==1:\n",
    "            grid[x,y]=island_tag\n",
    "            a=self.DFS(grid,x-1,y,m,n,island_tag)\n",
    "            b=self.DFS(grid,x,y-1,m,n,island_tag)\n",
    "            c=self.DFS(grid,x+1,y,m,n,island_tag)\n",
    "            d=self.DFS(grid,x,y+1,m,n,island_tag)\n",
    "            return 1+a+b+c+d\n",
    "        else:\n",
    "            return 0\n",
    "    def largestIsland(self, grid: List[List[int]]) -> int:\n",
    "        grid=np.array(grid)\n",
    "        m,n=grid.shape\n",
    "\n",
    "        island_tag=2\n",
    "\n",
    "        d={}\n",
    "        d[2]=1\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i,j]==1:\n",
    "                    d[island_tag]=self.DFS(grid,i,j,m,n,island_tag)\n",
    "                    island_tag+=1\n",
    "\n",
    "\n",
    "        sum_areas=[d[2]]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i,j]==0:\n",
    "                    tag=[0,0,0,0]\n",
    "                    if 0<=i-1<=m-1 and 0<=j<=n-1:\n",
    "                        tag[0]=grid[i-1,j]\n",
    "                    if 0<=i<=m-1 and 0<=j-1<=n-1:\n",
    "                        tag[1]=grid[i,j-1]\n",
    "                    if 0<=i+1<=m-1 and 0<=j<=n-1:\n",
    "                        tag[2]=grid[i+1,j]\n",
    "                    if 0<=i<=m-1 and 0<=j+1<=n-1:\n",
    "                        tag[3]=grid[i,j+1]\n",
    "                    tag=list(set(tag))# 去掉重复的岛\n",
    "                    if sum(tag)>0:\n",
    "                        area=1\n",
    "                        for x in tag:\n",
    "                            if x>0:\n",
    "                                area+=d[x]\n",
    "                        sum_areas.append(area)\n",
    "        return max(sum_areas)\n",
    "\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestIsland(self, grid: List[List[int]]) -> int:\n",
    "\n",
    "\n",
    "        \n",
    "        n = len(grid)\n",
    "        f = [[0]*n for i in range(n)]\n",
    "        index = [[0]*n for i in range(n)]\n",
    "        d = {}\n",
    "\n",
    "        def bfs(i,j,idx):\n",
    "            a = [1,-1,0,0]\n",
    "            b = [0,0,1,-1]\n",
    "            index[i][j] = idx\n",
    "            d[idx]+=1\n",
    "            f[i][j] = 1\n",
    "            for k in range(4):\n",
    "                ii = i+a[k]\n",
    "                jj = j+b[k]\n",
    "                # print(ii,jj)\n",
    "                if ii in range(n) and jj in range(n) and not f[ii][jj] and grid[ii][jj] == 1:\n",
    "                    print('in')\n",
    "                    bfs(ii,jj,idx)\n",
    "\n",
    "            \n",
    "        idx = 0\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if not f[i][j] and grid[i][j]==1:\n",
    "                    idx+=1\n",
    "                    d[idx] = 0\n",
    "                    # f[i][j] = 1\n",
    "                    bfs(i,j,idx)\n",
    "\n",
    "        # print(d)\n",
    "        # print(d.values())\n",
    "        dv = list(d.values())\n",
    "        if len(d) == 0:\n",
    "            return 1\n",
    "        m = max(dv)\n",
    "\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 0:\n",
    "                    a = [1,-1,0,0]\n",
    "                    b = [0,0,1,-1]\n",
    "                    s = []\n",
    "                    for k in range(4):\n",
    "                        ii = i+a[k]\n",
    "                        jj = j+b[k]\n",
    "                        if ii in range(n) and jj in range(n) and grid[ii][jj] == 1:\n",
    "                            s.append(index[ii][jj])\n",
    "                    s = set(s)\n",
    "                    r = 1\n",
    "                    for pos in s:\n",
    "                        r+=d[pos]\n",
    "                    m = max(m,r)\n",
    "\n",
    "        return m\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestIsland(self, grid: List[List[int]]) -> int:\n",
    "        UF = {}\n",
    "        def find(x):\n",
    "            UF.setdefault(x, x)\n",
    "            if x != UF[x]:\n",
    "                UF[x] = find(UF[x])\n",
    "            return UF[x]\n",
    "        def union(x, y):\n",
    "            UF.setdefault(x, x)\n",
    "            UF.setdefault(y, y)\n",
    "            UF[find(x)] = find(y)\n",
    "        \n",
    "        n,m = len(grid),len(grid[0])\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if j < m-1 and grid[i][j] == grid[i][j+1] == 1:\n",
    "                    union(i*m+j, i*m+j+1)\n",
    "                if i < n-1 and grid[i][j] == grid[i+1][j] == 1:\n",
    "                    union(i*m+j, (i+1)*m+j)\n",
    "        c = Counter()\n",
    "        ret = 0\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if grid[i][j]:\n",
    "                    c[find(i*m+j)] += 1\n",
    "                    ret = max(ret, c[find(i*m+j)])\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if grid[i][j] == 0:\n",
    "                    s = set()\n",
    "                    r = 1\n",
    "                    for u,v in [[i+1,j],[i-1,j],[i,j+1],[i,j-1]]:\n",
    "                        if u < 0 or u >= n or v < 0 or v >= m:\n",
    "                            continue\n",
    "                        if grid[u][v] and find(u*m+v) not in s:\n",
    "                            s.add(find(u*m+v))\n",
    "                            r += c[find(u*m+v)]\n",
    "                    ret = max(ret, r)\n",
    "        return ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestIsland(self, grid: List[List[int]]) -> int:\n",
    "        # 思路:\n",
    "        # 1. 首先算出grid已有的岛屿id和面积\n",
    "        # 2. 循环尝试，将不同i,j变为1后，max_area变化\n",
    "        ## 如果不分两步，会有重复计算，比如\n",
    "        # 1 0 1\n",
    "        # 0 1 0\n",
    "        # 0 1 0\n",
    "        # step 1\n",
    "        n = len(grid)\n",
    "        vis=[[0]*n for _ in range(n)]\n",
    "        root_id = [[0] * n for _ in range(n)] #存储(root_id, (i,j))\n",
    "        root_cnt = [0] * (n*n+1) \n",
    "        #print(root_cnt)\n",
    "        def dfs(i,j, idx, vis):\n",
    "            root_id[i][j] = idx\n",
    "            root_cnt[idx] += 1\n",
    "            vis[i][j] = 1\n",
    "            for d1,d2 in [[-1,0], [1,0], [0,-1], [0,1]]:\n",
    "                x,y=i+d1,j+d2\n",
    "                # 如果这里是flood - fill操作，就不需要vis数组\n",
    "                if 0<=x<n and 0<=y<n and grid[x][y] == 1 and not vis[x][y]:\n",
    "                    dfs(x,y,idx,vis)\n",
    "        idx=1\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1 and not vis[i][j]:\n",
    "                    #print('enter, i, j', i,j, idx)\n",
    "                    # root_id[i][j] = idx\n",
    "                    #print('root id mark', root_id)\n",
    "                    dfs(i,j, idx, vis)\n",
    "                    idx+=1\n",
    "        # print(root_id)\n",
    "        # print(root_cnt)\n",
    "\n",
    "        # step2:\n",
    "        max_area = max(root_cnt) #不用操作0的例子，比如[[1,1], [1,1]]\n",
    "        #vis 放在这里是错误的\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 0:\n",
    "                    vis = set()#存储root id, 访问过的不能访问，防止重复计算\n",
    "                    #print('enter second', i,j )\n",
    "                    ans = 1 #当前root的最大值统计\n",
    "                    for d1,d2 in [[-1,0], [1,0], [0,-1], [0,1]]:\n",
    "                        x,y=i+d1,j+d2\n",
    "                        if  0<=x<n and 0<=y<n:\n",
    "                            rid = root_id[x][y] \n",
    "                            if rid not in vis:\n",
    "                                cnt = root_cnt[rid]\n",
    "                                ans += cnt\n",
    "                            vis.add(rid)\n",
    "                    max_area = max(max_area, ans)\n",
    "        return max_area"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestIsland(self, grid: List[List[int]]) -> int:\n",
    "        # 需要两次遍历，一次获取所有岛屿及其面积，二次对0变1看能连接几个岛屿——加一个岛屿标记矩阵能够在不改变原矩阵的情况下不超时\n",
    "        # 特殊情况\n",
    "        if not grid:\n",
    "            return 0\n",
    "        que = deque()\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        visited = [[False] * n for _ in range(m)]\n",
    "        marked = [[-1] * n for _ in range(m)]\n",
    "        mark_num = 0\n",
    "        zeros = []\n",
    "        islands = {}\n",
    "        result = 0  # 在一次遍历中成为单个最大的岛屿\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 0:\n",
    "                    zeros.append((i, j))\n",
    "                elif grid[i][j] == 1 and not visited[i][j]:\n",
    "                    que.append((i, j))\n",
    "                    visited[i][j] = True\n",
    "                    marked[i][j] = mark_num\n",
    "                    temp = 1  # 临时变量，统计当前岛屿面积\n",
    "                    while len(que) > 0:\n",
    "                        x, y = que.popleft()\n",
    "                        for tx, ty in ((x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)):\n",
    "                            if 0 <= tx < m and 0 <= ty < n and not visited[tx][ty] and grid[tx][ty] == 1:\n",
    "                                que.append((tx, ty))\n",
    "                                visited[tx][ty] = True\n",
    "                                marked[tx][ty] = mark_num\n",
    "                                temp += 1\n",
    "                    islands[mark_num] = temp\n",
    "                    mark_num += 1\n",
    "                    result = max(result, temp)\n",
    "        # 二次对0变1看能连接几个岛屿\n",
    "        for x, y in zeros:\n",
    "            match_keys = set()  # 避免加入重复的key\n",
    "            for tx, ty in ((x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)):\n",
    "                if 0 <= tx < m and 0 <= ty < n and marked[tx][ty] in islands:\n",
    "                    match_keys.add(marked[tx][ty])\n",
    "            temp = 1  # 细节：加上自己，初始值设置为1\n",
    "            for k in match_keys:\n",
    "                temp += islands[k]\n",
    "            result = max(result, temp)\n",
    "        return result\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def largestIsland(self, grid: List[List[int]]) -> int:\r\n",
    "        R,C=len(grid),len(grid[0])\r\n",
    "        p=list(range(R*C))\r\n",
    "        sz=[1]*len(p)\r\n",
    "\r\n",
    "        def find(x):\r\n",
    "            if x!=p[x]:\r\n",
    "                p[x]=find(p[x])\r\n",
    "            return p[x]\r\n",
    "\r\n",
    "        def connect(x,y):\r\n",
    "            px,py=find(x),find(y)\r\n",
    "            if px==py:\r\n",
    "                return\r\n",
    "            p[px]=py\r\n",
    "            sz[py]+=sz[px]\r\n",
    "        \r\n",
    "        def size(x):\r\n",
    "            return sz[find(x)]\r\n",
    "        \r\n",
    "        get_id=lambda r,c:r*C+c\r\n",
    "\r\n",
    "        total=0\r\n",
    "        for r in range(R):\r\n",
    "            for c in range(C):\r\n",
    "                if grid[r][c]==0:\r\n",
    "                    continue\r\n",
    "                total+=1\r\n",
    "                if r-1>=0 and grid[r-1][c]:\r\n",
    "                    connect(get_id(r,c),get_id(r-1,c))\r\n",
    "                if c-1>=0 and grid[r][c-1]:\r\n",
    "                    connect(get_id(r,c),get_id(r,c-1))\r\n",
    "        \r\n",
    "        if total==R*C:\r\n",
    "            return total\r\n",
    "        \r\n",
    "        ret=0\r\n",
    "        dirs=[-1,0,1,0,-1]\r\n",
    "        for r in range(R):\r\n",
    "            for c in range(C):\r\n",
    "                if grid[r][c]:\r\n",
    "                    continue\r\n",
    "                cnt=1\r\n",
    "                counted=set()\r\n",
    "                for i in range(4):\r\n",
    "                    nr,nc=r+dirs[i],c+dirs[i+1]\r\n",
    "                    if nr<0 or nr==R or nc<0 or nc==C or grid[nr][nc]==0:\r\n",
    "                        continue\r\n",
    "                    idx=get_id(nr,nc)\r\n",
    "                    pid=find(idx)\r\n",
    "                    if pid in counted:\r\n",
    "                        continue\r\n",
    "                    cnt+=size(pid)\r\n",
    "                    counted.add(pid)\r\n",
    "                ret=max(ret,cnt)\r\n",
    "        return ret\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestIsland(self, grid: List[List[int]]) -> int:\n",
    "\n",
    "        def find(x):\n",
    "            if p[x] != x:\n",
    "                p[x] = find(p[x])\n",
    "            return p[x]\n",
    "\n",
    "        def union(a, b):\n",
    "            pa, pb = find(a), find(b)\n",
    "            if pa == pb:\n",
    "                return\n",
    "            p[pa] = pb\n",
    "            size[pb] += size[pa]\n",
    "\n",
    "        n = len(grid)\n",
    "        p = list(range(n * n))\n",
    "        size = [1] * (n * n)\n",
    "        for i, row in enumerate(grid):\n",
    "            for j, v in enumerate(row):\n",
    "                if v: # 如果 grid[i][j] = 1\n",
    "                    for a, b in [[0, -1], [-1, 0], [0, 1], [1, 0]]:\n",
    "                        x, y = i + a, j + b\n",
    "                        # 合并所有相邻的 1: 点 [x][y] and [i][j]\n",
    "                        if 0 <= x < n and 0 <= y < n and grid[x][y]:\n",
    "                            union(x * n + y, i * n + j)\n",
    "\n",
    "        ans = max(size)\n",
    "        for i, row in enumerate(grid):\n",
    "            for j, v in enumerate(row):\n",
    "                if v == 0: # 对于每个 0\n",
    "                    vis = set()\n",
    "                    t = 1\n",
    "                    for a, b in [[0, -1], [0, 1], [1, 0], [-1, 0]]:\n",
    "                        x, y = i + a, j + b\n",
    "                        if 0 <= x < n and 0 <= y < n and grid[x][y]:\n",
    "                            root = find(x * n + y) # 通过 find() 找到岛屿\n",
    "                            if root not in vis:\n",
    "                                vis.add(root)\n",
    "                                t += size[root] # 累加去重后的岛屿面积\n",
    "                    ans = max(ans, t)\n",
    "\n",
    "        return ans\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestIsland(self, grid: List[List[int]]) -> int:\n",
    "        def dfs(i, j):\n",
    "            if 0 <= i < M and 0 <= j < M and grid[i][j] == 1:\n",
    "                grid[i][j] = color\n",
    "                return 1 + dfs(i - 1, j) + dfs(i + 1, j) + dfs(i, j - 1) + dfs(i, j + 1)\n",
    "            return 0\n",
    "\n",
    "        M = len(grid)\n",
    "        color, color2Area = 2, {}\n",
    "        ans = 0\n",
    "        for i in range(M):\n",
    "            for j in range(M):\n",
    "                color2Area[color] = dfs(i, j)\n",
    "                ans = max(ans, color2Area[color])\n",
    "                color += 1\n",
    "        for i in range(M):\n",
    "            for j in range(M):\n",
    "                if grid[i][j] == 0:\n",
    "                    colors = set()\n",
    "                    for (di, dj) in [(-1, 0), (1, 0), (0, -1), (0, 1)]:\n",
    "                        ni, nj = i + di, j + dj\n",
    "                        if 0 <= ni < M and 0 <= nj < M:\n",
    "                            colors.add(grid[ni][nj])\n",
    "                    area = 1\n",
    "                    for color in colors:\n",
    "                        area += color2Area[color] if color != 0 else 0\n",
    "                    ans = max(ans, area)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self) -> None:\n",
    "        self.parent = dict()\n",
    "     \n",
    "    def find(self, p):\n",
    "        while self.parent[p][0]!=p:\n",
    "            self.parent[p] = self.parent[self.parent[p][0]]\n",
    "            p = self.parent[p][0]\n",
    "        return self.parent[p]\n",
    "    \n",
    "    def add(self, p):\n",
    "        if p in self.parent:\n",
    "            return\n",
    "        self.parent[p] = [p, 1]\n",
    "\n",
    "    def union(self, p1, p2):\n",
    "        r1, r2 = self.find(p1), self.find(p2)\n",
    "        if r1==r2:\n",
    "            return\n",
    "        r2[0] = r1[0]\n",
    "        r1[1] += r2[1]\n",
    "\n",
    "directions_half = [[-1, 0], [0, -1]]\n",
    "directions = [[-1, 0], [1, 0], [0, 1], [0, -1]]\n",
    "\n",
    "class Solution:\n",
    "    def largestIsland(self, grid: List[List[int]]) -> int:\n",
    "        uf = UnionFind()\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        zero = False\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j]==0:\n",
    "                    zero = True\n",
    "                    continue\n",
    "                p = (i, j)\n",
    "                uf.add(p)\n",
    "                for d in directions_half:\n",
    "                    ni, nj = i+d[0], j+d[1]\n",
    "                    if 0<=ni<m and 0<=nj<n and grid[ni][nj]==1:\n",
    "                        uf.union(p, (ni,nj))\n",
    "        if not zero:\n",
    "            return uf.find((0,0))[1]\n",
    "        r = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j]==1:\n",
    "                    continue\n",
    "                p = (i, j)\n",
    "                neighbors = set()\n",
    "                for d in directions:\n",
    "                    ni, nj = i+d[0], j+d[1]\n",
    "                    if ni<0 or ni>=m or nj<0 or nj>=n:\n",
    "                        continue\n",
    "                    if grid[ni][nj]!=1:\n",
    "                        continue\n",
    "                    neighbors.add(uf.find((ni, nj))[0])\n",
    "                size = 1+sum(uf.find(r)[1] for r in neighbors)\n",
    "                r = max(r, size)\n",
    "        return r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestIsland(self, grid: List[List[int]]) -> int:\n",
    "        if len(grid) == 0:\n",
    "            return 0\n",
    "\n",
    "        n = len(grid)\n",
    "        size = [0] * (n * n + 2)\n",
    "        parent = [i for i in range(n * n + 2)]\n",
    "\n",
    "        def find(x):\n",
    "            if parent[x] != x:\n",
    "                parent[x] = find(parent[x])\n",
    "            return parent[x]\n",
    "\n",
    "        def union(x, y):\n",
    "            root_x = find(x)\n",
    "            root_y = find(y)\n",
    "            if root_x != root_y:\n",
    "                parent[root_x] = root_y\n",
    "                size[root_y] += size[root_x]\n",
    "\n",
    "        def dfs(i, j, index):\n",
    "            nonlocal grid, size\n",
    "            grid[i][j] = index\n",
    "            size[index] += 1\n",
    "            for dx, dy in [(0, 1), (0, -1), (-1, 0), (1, 0)]:\n",
    "                x = i + dx\n",
    "                y = j + dy\n",
    "                if 0 <= x < n and 0 <= y < n and grid[x][y] == 1:\n",
    "                    dfs(x, y, index)\n",
    "\n",
    "        index = 2\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1:\n",
    "                    dfs(i, j, index)\n",
    "                    index += 1\n",
    "\n",
    "        res = max(size)\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 0:\n",
    "                    connected_islands = set()\n",
    "                    for dx, dy in [(0, 1), (0, -1), (-1, 0), (1, 0)]:\n",
    "                        x = i + dx\n",
    "                        y = j + dy\n",
    "                        if 0 <= x < n and 0 <= y < n and grid[x][y] != 0:\n",
    "                            connected_islands.add(find(grid[x][y]))\n",
    "                    res = max(res, sum(size[idx] for idx in connected_islands) + 1)\n",
    "\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self, grid):\n",
    "        self.father = {}\n",
    "        self.area = {}\n",
    "        \n",
    "    def find(self, x):\n",
    "        self.father.setdefault(x, x)\n",
    "        if self.father[x] != x:\n",
    "            self.father[x] = self.find(self.father[x])\n",
    "        return self.father[x]\n",
    "    \n",
    "    def union(self, x, y):\n",
    "        root_x, root_y = self.find(x), self.find(y)\n",
    "        if root_x != root_y:\n",
    "            self.father[root_x] = root_y\n",
    "            self.area[root_y] += self.area[root_x]\n",
    "            del self.area[root_x]\n",
    "        return self.area[root_y]\n",
    "\n",
    "    def set_area(self, x):\n",
    "        self.area[x] = 1\n",
    "class Solution:\n",
    "    def largestIsland(self,grid):\n",
    "        directions = [(0, 1), (0, -1), (-1, 0), (1, 0)]\n",
    "        n = len(grid)\n",
    "        uf = UnionFind(grid)\n",
    "        \n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1:\n",
    "                    uf.set_area((i, j))\n",
    "\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1:\n",
    "                    for dx, dy in directions:\n",
    "                        nx, ny = i + dx, j + dy\n",
    "                        if 0 <= nx < n and 0 <= ny < n and grid[nx][ny] == 1:\n",
    "                            uf.union((i, j), (nx, ny))\n",
    "\n",
    "        res = max(uf.area.values() if uf.area else [0])\n",
    "\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 0:\n",
    "                    seen = set()\n",
    "                    for dx, dy in directions:\n",
    "                        nx, ny = i + dx, j + dy\n",
    "                        if 0 <= nx < n and 0 <= ny < n and grid[nx][ny] == 1:\n",
    "                            root = uf.find((nx, ny))\n",
    "                            if root not in seen:\n",
    "                                seen.add(root)\n",
    "                    res = max(res, 1 + sum(uf.area[root] for root in seen))\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self, grid):\n",
    "        self.father = {}\n",
    "        self.area = {}\n",
    "        \n",
    "    def find(self, x):\n",
    "        self.father.setdefault(x, x)\n",
    "        if self.father[x] != x:\n",
    "            self.father[x] = self.find(self.father[x])\n",
    "        return self.father[x]\n",
    "    \n",
    "    def union(self, x, y):\n",
    "        root_x, root_y = self.find(x), self.find(y)\n",
    "        if root_x != root_y:\n",
    "            self.father[root_x] = root_y\n",
    "            self.area[root_y] += self.area[root_x]\n",
    "            del self.area[root_x]\n",
    "        return self.area[root_y]\n",
    "\n",
    "    def set_area(self, x):\n",
    "        self.area[x] = 1\n",
    "class Solution:\n",
    "    def largestIsland(self, grid: List[List[int]]) -> int:\n",
    "        directions = [(0, 1), (0, -1), (-1, 0), (1, 0)]\n",
    "        n = len(grid)\n",
    "        uf = UnionFind(grid)\n",
    "        \n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1:\n",
    "                    uf.set_area((i, j))\n",
    "\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1:\n",
    "                    for dx, dy in directions:\n",
    "                        nx, ny = i + dx, j + dy\n",
    "                        if 0 <= nx < n and 0 <= ny < n and grid[nx][ny] == 1:\n",
    "                            uf.union((i, j), (nx, ny))\n",
    "\n",
    "        res = max(uf.area.values() if uf.area else [0])\n",
    "\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 0:\n",
    "                    seen = set()\n",
    "                    for dx, dy in directions:\n",
    "                        nx, ny = i + dx, j + dy\n",
    "                        if 0 <= nx < n and 0 <= ny < n and grid[nx][ny] == 1:\n",
    "                            root = uf.find((nx, ny))\n",
    "                            if root not in seen:\n",
    "                                seen.add(root)\n",
    "                    res = max(res, 1 + sum(uf.area[root] for root in seen))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.order = -1\n",
    "        self.area = 0\n",
    "        self.surround = []\n",
    "\n",
    "    def largestIsland(self, grid: list[list[int]]) -> int:\n",
    "        row, col = len(grid), len(grid[0])\n",
    "        total = 0\n",
    "        for i in range(row):\n",
    "            for j in range(col):\n",
    "                total += grid[i][j]\n",
    "        if total >= row * col - 1:\n",
    "            return row * col\n",
    "\n",
    "        Area = []\n",
    "        Surround = {}\n",
    "        visited = [[0] * col for _ in range(row)]\n",
    "\n",
    "        def dfs(x, y):\n",
    "            for m, n in [[x + 1, y], [x - 1, y], [x, y + 1], [x, y - 1]]:\n",
    "                if m < 0 or m >= row or n < 0 or n >= col:\n",
    "                    continue\n",
    "                if visited[m][n] == 0:\n",
    "                    if grid[m][n] == 1:\n",
    "                        self.area += 1\n",
    "                        visited[m][n] = 1\n",
    "                        dfs(m, n)\n",
    "                    else:\n",
    "                        if [m,n] not in self.surround:\n",
    "                            self.surround.append([m, n])\n",
    "\n",
    "        for i in range(row):\n",
    "            for j in range(col):\n",
    "                if visited[i][j] == 0 and grid[i][j] == 1:\n",
    "                    self.order += 1\n",
    "                    self.area = 1\n",
    "                    self.surround = []\n",
    "                    visited[i][j] = 1\n",
    "                    dfs(i, j)\n",
    "                    Area.append(self.area)\n",
    "                    Surround[self.order] = self.surround\n",
    "\n",
    "        val = [[1]*col for _ in range(row)]\n",
    "        for key in Surround.keys():\n",
    "            for m,n in Surround[key]:\n",
    "                val[m][n] += Area[key]\n",
    "        max_area = 1\n",
    "        for i in range(row):\n",
    "            for j in range(col):\n",
    "                if val[i][j] > max_area:\n",
    "                    max_area = val[i][j]\n",
    "\n",
    "        return max_area"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.length=0\n",
    "        self.root={}\n",
    "        self.size={(-1,-1):1}\n",
    "        self.rank={}\n",
    "    def find(self,pos):\n",
    "        if self.root.get(pos) is None:\n",
    "            return (-1,-1)\n",
    "        if self.root[pos]!=pos:\n",
    "            self.root[pos]=self.find(self.root[pos])\n",
    "        return self.root[pos]\n",
    "    def merge(self,pos1,pos2):\n",
    "        x=self.find(pos1)\n",
    "        y=self.find(pos2)\n",
    "        if x==y:\n",
    "            return\n",
    "        if self.rank[x]<self.rank[y]:\n",
    "            self.root[x]=y\n",
    "            self.size[y]+=self.size[x]\n",
    "            self.size.pop(x)\n",
    "        elif self.rank[x]>=self.rank[y]:\n",
    "            self.root[y]=x\n",
    "            self.size[x]+=self.size[y]\n",
    "            self.size.pop(y)\n",
    "            if self.rank[x]==self.rank[y]:\n",
    "                self.rank[x]+=1\n",
    "    def largestIsland(self, grid: List[List[int]]) -> int:\n",
    "        n=len(grid)\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                pos=(i,j)\n",
    "                if grid[i][j]==1:\n",
    "                    if self.root.get(pos) is None:\n",
    "                        self.root[pos]=pos\n",
    "                        self.rank[pos]=1\n",
    "                        self.size[pos]=1\n",
    "                    if i>0 and grid[i-1][j]==1 and self.root.get((i-1,j)):\n",
    "                        self.merge(pos,(i-1,j))\n",
    "                    if j>0 and grid[i][j-1]==1 and self.root.get((i,j-1)):\n",
    "                        self.merge(pos,(i,j-1))\n",
    "        # dp=[[{} for j in range(n)] for i in range(n)]\n",
    "        # for i in range(n):\n",
    "        #     for j in range(n):\n",
    "        #         pos=(i,j)\n",
    "        #         if grid[i][j]==1:\n",
    "        #             if i<n-1 and grid[i+1][j]==1 and self.find(pos)!=self.find((i+1,j)):\n",
    "        #                 self.merge(pos,(i+1,j))\n",
    "        #             if i>0 and grid[i-1][j]==1 and self.find(pos)!=self.find((i-1,j)):\n",
    "        #                 self.merge(pos,(i-1,j))\n",
    "        #             if j<n-1 and grid[i][j+1]==1 and self.find(pos)!=self.find((i,j+1)):\n",
    "        #                 self.merge(pos,(i,j+1))\n",
    "        #             if j>0 and grid[i][j-1]==1 and self.find(pos)!=self.find((i,j-1)):\n",
    "        #                 self.merge(pos,(i,j-1))\n",
    "        best=0\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                pos=(i,j)\n",
    "                # dp[i][j][self.find(pos)]=self.size[self.find(pos)]\n",
    "                if grid[i][j]==1:\n",
    "                    # dp[i][j]=self.size[self.find(pos)]\n",
    "                    tmp=self.size[self.find(pos)]\n",
    "                elif grid[i][j]==0:\n",
    "                    tmp=1\n",
    "                    vis=[]\n",
    "                    if i<n-1 and grid[i+1][j]==1:\n",
    "                        r=self.find((i+1,j))\n",
    "                        if r not in vis:\n",
    "                            tmp+=self.size[r]\n",
    "                            vis.append(r)\n",
    "                    if i>0 and grid[i-1][j]==1:\n",
    "                        r=self.find((i-1,j))\n",
    "                        if r not in vis:\n",
    "                            tmp+=self.size[r]\n",
    "                            vis.append(r)\n",
    "                    if j<n-1 and grid[i][j+1]==1:\n",
    "                        r=self.find((i,j+1))\n",
    "                        if r not in vis:\n",
    "                            tmp+=self.size[r]\n",
    "                            vis.append(r)\n",
    "                    if j>0 and grid[i][j-1]==1:\n",
    "                        r=self.find((i,j-1))\n",
    "                        if r not in vis:\n",
    "                            tmp+=self.size[r]\n",
    "                            vis.append(r)\n",
    "                best=max(tmp,best)\n",
    "        return best"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestIsland(self, grid: List[List[int]]) -> int:\n",
    "        n = len(grid)\n",
    "        roots = list(range(n * n))\n",
    "        sizes = [1] * (n * n)\n",
    "        def find(x):\n",
    "            if roots[x] != x:\n",
    "                roots[x] = find(roots[x])\n",
    "            return roots[x]\n",
    "        def union(x, y):\n",
    "            rx, ry = find(x), find(y)\n",
    "            if rx != ry:\n",
    "                if sizes[rx] > sizes[ry]: rx, ry = ry, rx\n",
    "                roots[rx] = ry\n",
    "                sizes[ry] += sizes[rx]\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1:\n",
    "                    for ni, nj in (i + 1, j), (i, j + 1):\n",
    "                        if n > ni >= 0 <= nj < n and grid[ni][nj] == 1:\n",
    "                            union(i * n + j, ni * n + nj)\n",
    "        ans = max(sizes)\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 0:\n",
    "                    cnt = 1\n",
    "                    ha = set()\n",
    "                    for ni, nj in (i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1):\n",
    "                        if n > ni >= 0 <= nj < n and grid[ni][nj] == 1:\n",
    "                            fa = find(ni * n + nj)\n",
    "                            if fa not in ha:\n",
    "                                cnt += sizes[fa]\n",
    "                                ha.add(fa)\n",
    "                    ans = max(ans, cnt)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestIsland(self, grid: List[List[int]]) -> int:\n",
    "        parents = dict()\n",
    "        cnt = dict()\n",
    "        row, col = len(grid), len(grid[0])\n",
    "        dir = ((1, 0), (-1, 0), (0, -1), (0, 1))\n",
    "        for i in range(row):\n",
    "            for j in range(col):\n",
    "                if grid[i][j] == 1 and (i, j) not in parents:\n",
    "                    parents[(i, j)] = (i, j)\n",
    "                    current = [(i, j)]\n",
    "                    start, end = 0, 1\n",
    "                    while start < end:\n",
    "                        while start < end:\n",
    "                            x,y = current[start]\n",
    "                            for dx, dy in dir:\n",
    "                                nx, ny = x + dx, y + dy\n",
    "                                if nx >= 0 and nx < row and ny >= 0 and ny < col and grid[nx][ny] == 1 and (nx, ny) not in parents:\n",
    "                                    current.append((nx, ny))\n",
    "                                    parents[(nx, ny)] = (i, j)\n",
    "                            start += 1\n",
    "                        start = end\n",
    "                        end = len(current)\n",
    "                    cnt[(i, j)] = len(current)\n",
    "                    if len(current) == row * col:\n",
    "                        return row * col\n",
    "\n",
    "        res = 1\n",
    "        for i in range(row):\n",
    "            for j in range(col):\n",
    "                if grid[i][j] == 0:\n",
    "                    cur = 1\n",
    "                    pset = set()\n",
    "                    for dx, dy in dir:\n",
    "                        nx, ny = i + dx, j + dy\n",
    "                        if nx >= 0 and nx < row and ny >= 0 and ny < col and grid[nx][ny] == 1:\n",
    "                            pset.update({parents[(nx, ny)]})\n",
    " \n",
    "                    for p in pset:\n",
    "                        cur += cnt[p]\n",
    "                    res = max(res, cur)\n",
    "\n",
    "        return res\n",
    "\n",
    "\n",
    "                        \n",
    "                    \n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def largestIsland(self, grid):\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        if sum(sum(grid[row]) for row in range(m)) == m*n:\n",
    "            return m*n\n",
    "\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        mask = [[0 for _ in range(n)] for _ in range(m)]\n",
    "        visted = [[0 for _ in range(n)] for _ in range(m)]\n",
    "\n",
    "        def dfs(p, q, land_space, count):\n",
    "            for (x,y) in [(p,q-1),(p,q+1),(p-1,q),(p+1,q)]:\n",
    "                if (0<=x<m) and (0<=y<n) and (grid[x][y]==1) and (visted[x][y]==0):\n",
    "                    visted[x][y] = 1\n",
    "                    land_space += 1\n",
    "                    mask[x][y] = count\n",
    "                    land_space = dfs(x, y, land_space, count)\n",
    "            return land_space\n",
    "\n",
    "        # 记录每一块的面积\n",
    "        dic = dict()\n",
    "        max_space = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if (visted[i][j]==0) and (grid[i][j] == 1):\n",
    "                    visted[i][j] = 1\n",
    "                    count = i*n+j+1\n",
    "                    land_space = 1\n",
    "                    mask[i][j] = count\n",
    "                    space = dfs(i, j, land_space, count)\n",
    "                    dic[count] = space\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 0:\n",
    "                    s = set()\n",
    "                    for (x,y) in [(i,j-1),(i,j+1),(i-1,j),(i+1,j)]:\n",
    "                        if (0<=x<m) and (0<=y<n):\n",
    "                            s.add(mask[x][y])\n",
    "                    lst = list(s)\n",
    "                    # space_tmp = sum(dic[p] for p in lst)lst\n",
    "                    space_tmp = sum(dic.get(p, 0) for p in lst) + 1\n",
    "                    if space_tmp > max_space:\n",
    "                        max_space = space_tmp\n",
    "\n",
    "        return max_space"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.temp = 0\n",
    "        self.area = 0\n",
    "        self.dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]]\n",
    "    \n",
    "    def dfs(self, grid, visited, x, y, mark):\n",
    "        for dir in self.dirs:\n",
    "            nextx = x + dir[0]\n",
    "            nexty = y + dir[1]\n",
    "            if nextx < 0 or nextx >= len(grid) or nexty < 0 or nexty >= len(grid[0]):\n",
    "                continue\n",
    "            if grid[nextx][nexty] == 1 and visited[nextx][nexty] == 0:\n",
    "                visited[nextx][nexty] = mark\n",
    "                self.temp += 1\n",
    "                self.dfs(grid, visited, nextx, nexty, mark)\n",
    "\n",
    "    def largestIsland(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        visited = [[0] * n for _ in range(m)]\n",
    "        area = Counter()\n",
    "        \n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                mark = i * n + j + 1\n",
    "                if visited[i][j] == 0 and grid[i][j] == 1:\n",
    "                    visited[i][j] = mark\n",
    "                    self.temp = 1\n",
    "                    self.dfs(grid, visited, i, j, mark)\n",
    "                area[mark] = self.temp\n",
    "                self.area = max(self.area, self.temp)\n",
    "        \n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 0:\n",
    "                    self.temp = 1\n",
    "                    connected = set()\n",
    "                    for dir in self.dirs:\n",
    "                        nextx = i + dir[0]\n",
    "                        nexty = j + dir[1]\n",
    "                        if 0 <= nextx < m and 0 <= nexty < n and grid[nextx][nexty] == 1 and visited[nextx][nexty] not in connected:\n",
    "                            self.temp += area[visited[nextx][nexty]]\n",
    "                            connected.add(visited[nextx][nexty])\n",
    "\n",
    "                    self.area = max(self.area, self.temp)\n",
    "                    \n",
    "        return self.area"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestIsland(self, grid: List[List[int]]) -> int:\n",
    "        total_dict = dict()\n",
    "        total_dict['count'] = 0\n",
    "        def bfs(x0, y0):\n",
    "            stack = [(x0, y0)]\n",
    "            res = 1\n",
    "            s = set()\n",
    "            stack_list = [(x0, y0)]\n",
    "            s.add((x0, y0))\n",
    "            while stack:\n",
    "                for i in range(len(stack)):\n",
    "                    x0, y0 = stack.pop(0)\n",
    "                    for dx, dy in [(-1, 0), (1, 0), (0, 1), (0, -1)]:\n",
    "                        x = x0 + dx\n",
    "                        y = y0 + dy\n",
    "                        if x >= 0 and x < len(grid) and y >= 0 and y < len(grid[0]):\n",
    "                            if grid[x][y] == 1 and (x, y) not in s:\n",
    "                                s.add((x, y))\n",
    "                                stack.append((x, y))\n",
    "                                stack_list.append((x, y))\n",
    "                                res += 1\n",
    "            for key in stack_list:\n",
    "                total_dict[key] = [res, total_dict['count']]\n",
    "            total_dict['count'] += 1\n",
    "                \n",
    "            return res\n",
    "        result = 0\n",
    "        for i in range(len(grid)):\n",
    "            for j in range(len(grid[0])):\n",
    "                if grid[i][j] == 1:\n",
    "                    if (i, j) in total_dict.keys():\n",
    "                        result = max(result, total_dict[(i, j)][0])\n",
    "                    else:\n",
    "                        result = max(result, bfs(i, j))\n",
    "        for i in range(len(grid)):\n",
    "            for j in range(len(grid[0])):\n",
    "                if grid[i][j] == 0:\n",
    "                    s = set()\n",
    "                    res = 0\n",
    "                    for dx, dy in [(-1, 0), (1, 0), (0, 1), (0, -1)]:\n",
    "                        x = i + dx\n",
    "                        y = j + dy\n",
    "                        if x >= 0 and x < len(grid) and y >= 0 and y < len(grid[0]):\n",
    "                            if (x, y) in total_dict.keys() and total_dict[(x, y)][1] not in s:\n",
    "                                res += total_dict[(x, y)][0]\n",
    "                                s.add(total_dict[(x, y)][1])\n",
    "                    result = max(result, res + 1)\n",
    "        return result\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestIsland(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        visited = [ [False for _ in range(n)] for _ in range(m)]\n",
    "        direction = [(-1,0),(1,0),(0,-1),(0,1)]\n",
    "        \n",
    "        ares = {}\n",
    "        island_id = 2\n",
    "        res = 0\n",
    "        global count\n",
    "        count = 0\n",
    "\n",
    "        def dfs(grid, x, y, island_id):\n",
    "            if grid[x][y] == 0 or visited[x][y]:\n",
    "                return \n",
    "            visited[x][y] = True\n",
    "            grid[x][y] = island_id\n",
    "            global count \n",
    "            count = count + 1\n",
    "            for d in direction:\n",
    "                nextx = x + d[0]\n",
    "                nexty = y + d[1]\n",
    "                if nextx < 0 or nextx > m - 1 or nexty < 0 or nexty > n - 1 or grid[nextx][nexty] == 0 or visited[nextx][nexty]:\n",
    "                    continue\n",
    "                dfs(grid, nextx, nexty, island_id)\n",
    "\n",
    "        # 第一次遍历计算面积 n*n\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                count = 0\n",
    "                dfs(grid, i, j, island_id)\n",
    "                ares[island_id] = count\n",
    "                island_id += 1\n",
    "                res = max(res, count)\n",
    "        \n",
    "        if res == n * m:\n",
    "            return res\n",
    "        # 第二次遍历 翻转，计算最大岛屿\n",
    "        \n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j]==0:\n",
    "                    hased = set()#记录已经遍历了的岛屿\n",
    "                    count = 1#初始化为1是因为把当前位置初始化为1了\n",
    "                    for d in direction:\n",
    "                        nexti = i + d[0]\n",
    "                        nextj = j + d[1]\n",
    "                        if nexti < 0 or nexti > m - 1 or nextj < 0 or nextj > n - 1:\n",
    "                            continue\n",
    "                        # 访问过或者周围没有岛屿，则直接跳过\n",
    "                        if grid[nexti][nextj] in hased or grid[nexti][nextj] not in ares.keys():\n",
    "                            continue\n",
    "                        hased.add(grid[nexti][nextj])\n",
    "                        count += ares[grid[nexti][nextj]]\n",
    "                    res = max(count, res)                       \n",
    "        return res\n",
    "              "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.order = -1\n",
    "        self.area = 0\n",
    "        self.surround = set()\n",
    "\n",
    "    def largestIsland(self, grid: list[list[int]]) -> int:\n",
    "        row, col = len(grid), len(grid[0])\n",
    "        total = 0\n",
    "        for i in range(row):\n",
    "            for j in range(col):\n",
    "                total += grid[i][j]\n",
    "        if total >= row * col - 1:\n",
    "            return row * col\n",
    "\n",
    "        Area = []\n",
    "        Surround = {}\n",
    "        visited = [[0] * col for _ in range(row)]\n",
    "\n",
    "        def dfs(x, y):\n",
    "            for m, n in [(x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)]:\n",
    "                if m < 0 or m >= row or n < 0 or n >= col:\n",
    "                    continue\n",
    "                if visited[m][n] == 0:\n",
    "                    if grid[m][n] == 1:\n",
    "                        self.area += 1\n",
    "                        visited[m][n] = 1\n",
    "                        dfs(m, n)\n",
    "                    else:\n",
    "                        self.surround.add((m, n))\n",
    "\n",
    "        for i in range(row):\n",
    "            for j in range(col):\n",
    "                if visited[i][j] == 0 and grid[i][j] == 1:\n",
    "                    self.order += 1\n",
    "                    self.area = 1\n",
    "                    self.surround = set()\n",
    "                    visited[i][j] = 1\n",
    "                    dfs(i, j)\n",
    "                    Area.append(self.area)\n",
    "                    Surround[self.order] = self.surround\n",
    "\n",
    "        val = [[1] * col for _ in range(row)]\n",
    "        for key in Surround.keys():\n",
    "            for m, n in Surround[key]:\n",
    "                val[m][n] += Area[key]\n",
    "        max_area = 1\n",
    "        for i in range(row):\n",
    "            for j in range(col):\n",
    "                if val[i][j] > max_area:\n",
    "                    max_area = val[i][j]\n",
    "\n",
    "        return max_area"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestIsland(self, grid: List[List[int]]) -> int:\n",
    "        n, m = len(grid), len(grid[0])\n",
    "        visited = [[False] * m for _ in range(n)]\n",
    "        dirs = [[0,1], [0,-1], [1,0], [-1,0]]\n",
    "        islandArea = {}\n",
    "        number = 0\n",
    "        res = []\n",
    "\n",
    "        def bfs(x, y, number):\n",
    "            deque = [(x, y)]\n",
    "            visited[x][y] = True\n",
    "            temp = [(x, y)]\n",
    "            while len(deque) > 0:\n",
    "                x, y = deque.pop()\n",
    "                for i in range(4):\n",
    "                    xn = x + dirs[i][0]\n",
    "                    yn = y + dirs[i][1]\n",
    "                    if xn < 0 or xn >= n or yn < 0 or yn >= m:\n",
    "                        continue\n",
    "                    if visited[xn][yn] or grid[xn][yn] == 0:\n",
    "                        continue\n",
    "                    deque.append((xn, yn))\n",
    "                    temp.append((xn, yn))\n",
    "                    visited[xn][yn] = True\n",
    "            if len(temp) > 0:\n",
    "                for x, y in temp:\n",
    "                    islandArea[(x, y)] = [number, len(temp)]\n",
    "                number += 1\n",
    "                res.append(len(temp))\n",
    "            return number\n",
    "        \n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if not visited[i][j] and grid[i][j] == 1:\n",
    "                    number = bfs(i, j, number)\n",
    "\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if grid[i][j] == 0:\n",
    "                    temp = set()\n",
    "                    tempArea = 0\n",
    "                    for k in range(4):\n",
    "                        xn = i + dirs[k][0]\n",
    "                        yn = j + dirs[k][1]\n",
    "                        if xn < 0 or xn >= n or yn < 0 or yn >= m:\n",
    "                            continue\n",
    "                        if (xn, yn) in islandArea and islandArea[(xn, yn)][0] not in temp:\n",
    "                            tempArea += islandArea[(xn, yn)][1]\n",
    "                            temp.add(islandArea[(xn, yn)][0])\n",
    "                    res.append(tempArea + 1)\n",
    "\n",
    "        return max(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class UF:\n",
    "    def __init__(self, n):\n",
    "        parent = []\n",
    "        size = [1] * n\n",
    "        for i in range(n):\n",
    "            parent.append(i)\n",
    "\n",
    "        self.parent = parent\n",
    "        self.size = size\n",
    "\n",
    "    def find(self, x):\n",
    "        parent = self.parent\n",
    "        while x != parent[x]:\n",
    "            parent[x] = self.find(parent[x])\n",
    "            x = parent[x]\n",
    "        return x\n",
    "    \n",
    "    def union(self, u, v):\n",
    "        root_u = self.find(u)\n",
    "        root_v = self.find(v)\n",
    "        if root_u == root_v:\n",
    "            return\n",
    "        self.parent[root_v] = root_u\n",
    "        self.size[root_u] += self.size[root_v]\n",
    "    \n",
    "    def is_union(self, u, v):\n",
    "        return self.find(u) == self.find(v)\n",
    "    \n",
    "    def get_size(self, u):\n",
    "        return self.size[self.find(u)]\n",
    "    \n",
    "    def get_parent(self, u):\n",
    "        return self.find(u)\n",
    "    \n",
    "class Solution:\n",
    "    def largestIsland(self, grid: List[List[int]]) -> int:\n",
    "        n = len(grid)\n",
    "        temp = n * n\n",
    "        uf = UF(temp)\n",
    "        visited = []\n",
    "        for i in range(n):\n",
    "            visited.append([False] * n)\n",
    "\n",
    "        def get_key(i, j):\n",
    "            return i * n + j\n",
    "        \n",
    "        def traverse(pi, pj, i, j): # pi，pj是初始节点的坐标，i，j是当前节点的坐标\n",
    "            if i<0 or j<0 or i>=n or j >= n: # 超过边界不用判断\n",
    "                return\n",
    "            if grid[i][j] == 0: # 水不用判断\n",
    "                return\n",
    "            if visited[i][j]: # 访问过的不用判断\n",
    "                return\n",
    "            visited[i][j] = True\n",
    "            uf.union(get_key(pi, pj), get_key(i, j))\n",
    "            traverse(pi, pj, i-1, j)\n",
    "            traverse(pi, pj, i+1, j)\n",
    "            traverse(pi, pj, i, j-1)\n",
    "            traverse(pi, pj, i, j+1)\n",
    "\n",
    "        def get_parent_and_size(i, j):\n",
    "            return uf.get_size(get_key(i, j)), uf.get_parent(get_key(i, j))\n",
    "\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 0:\n",
    "                    continue\n",
    "                if visited[i][j]:\n",
    "                    continue\n",
    "                traverse(i, j, i, j)\n",
    "        max_m = 0\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1:\n",
    "                    max_m = max(max_m, uf.get_size(get_key(i, j)))\n",
    "                    continue\n",
    "                # 如果是水\n",
    "                parent_list = []\n",
    "                size_list = []\n",
    "                for k, l in [(i-1, j), (i+1, j), (i, j-1), (i, j+1)]:\n",
    "                    if k<0 or l<0 or k>=n or l >= n: # 超过边界不用判断\n",
    "                        continue\n",
    "                    if grid[k][l] == 0:\n",
    "                        continue\n",
    "                    lsize, lparent = get_parent_and_size(k, l)\n",
    "                    if lparent in parent_list:\n",
    "                        continue\n",
    "                    size_list.append(lsize)\n",
    "                    parent_list.append(lparent)\n",
    "\n",
    "                size_list.sort(reverse=True)\n",
    "                if not size_list:\n",
    "                    max_m = max(max_m, 1)\n",
    "                else:\n",
    "                    max_m = max(max_m, sum(size_list)+1)\n",
    "        return max_m\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestIsland(self, grid: List[List[int]]) -> int:\n",
    "        n,m=len(grid),len(grid[0])\n",
    "        fi=[[1,k] for k in range(n*m)]\n",
    "        seen=set()\n",
    "        def find(node,f):\n",
    "            if f[node][1]!=node:\n",
    "                f[node][1]=find(f[node][1],f)\n",
    "            return f[node][1]\n",
    "        def emerge(a,b,mx,f):\n",
    "            #print(a,b,f)\n",
    "            af=find(a,f)\n",
    "            bf=find(b,f)\n",
    "            if bf!=af:\n",
    "                f[bf][1],f[af][0]=f[af][1],f[bf][0]+f[af][0]\n",
    "                #print(af,f[af])\n",
    "                mx=max(f[af][0],mx)\n",
    "            return mx\n",
    "        def emr(i,j,f):\n",
    "            nonlocal mx,seen\n",
    "            if i*m+j in seen:\n",
    "                return\n",
    "            seen.add(i*m+j)\n",
    "            for p,q in [[i-1,j],[i,j-1],[i+1,j],[i,j+1]]:\n",
    "                    if( p*m+q not in seen and 0<=p<n and 0<=q<m and grid[p][q]==1):\n",
    "                        mx=emerge(i*m+j,p*m+q,mx,f) \n",
    "                        emr(p,q,f)\n",
    "            \n",
    "             \n",
    "        mx=1\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j]==0:\n",
    "                    continue\n",
    "                emr(i,j,fi)\n",
    "       \n",
    "        #print(mx)\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j]==0:\n",
    "                    con=set() \n",
    "                    temp=1\n",
    "                    for p,q in [[i-1,j],[i,j-1],[i+1,j],[i,j+1]]:\n",
    "                        if(0<=p<n and 0<=q<m and grid[p][q]==1):\n",
    "                            fn=find(p*m+q,fi)\n",
    "                            if fn not in con:\n",
    "                                temp+=fi[fn][0]\n",
    "                                #print(i,j,p,q,temp,fn,fi[fn])\n",
    "                                con.add(fn)\n",
    "                    mx=max(mx,temp)\n",
    "                            \n",
    "        return mx\n",
    "\n",
    "        \n",
    "        \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestIsland(self, grid: List[List[int]]) -> int:\n",
    "        n = len(grid)\n",
    "        lands = set((i, j) for i in range(n) for j in range(n) if grid[i][j] == 1)\n",
    "        waters = set((i, j) for i in range(n) for j in range(n) if grid[i][j] == 0)\n",
    "        link = {}\n",
    "        if not lands:\n",
    "            return 1\n",
    "        if not waters:\n",
    "            return n**2\n",
    "        while lands:\n",
    "            island = set()\n",
    "            water = set()\n",
    "            d = lands.pop()\n",
    "            island.add(d)\n",
    "            count = 1\n",
    "            while island:\n",
    "                # print(island)\n",
    "                neigh = set()\n",
    "                for dot in island:\n",
    "                    neigh |= set([(dot[0]-1, dot[1]), (dot[0]+1, dot[1]), (dot[0], dot[1]-1), (dot[0], dot[1]+1)])\n",
    "                water |= neigh&waters\n",
    "                neigh &= lands\n",
    "                lands -= neigh\n",
    "                count += len(neigh)\n",
    "                island = neigh\n",
    "            for dot in water:\n",
    "                link[dot] = link.get(dot, 1) + count\n",
    "        return max(i for i in link.values())\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestIsland(self, grid: List[List[int]]) -> int:\n",
    "        n = len(grid)\n",
    "        uf = UnionFind(n*n)\n",
    "        zeros = []\n",
    "\n",
    "        def get_id(i,j):\n",
    "            return i*n + j\n",
    "\n",
    "        for i,row in enumerate(grid):\n",
    "            for j,x in enumerate(row):\n",
    "                if x:\n",
    "                    if i > 0 and grid[i - 1][j]:\n",
    "                        uf.union((i - 1)*n + j,i * n + j)\n",
    "                    if j > 0 and grid[i][j - 1]:\n",
    "                        uf.union(i * n + j,i * n + j - 1)\n",
    "                else:\n",
    "                    zeros.append((i,j))\n",
    "\n",
    "        ans = max(uf.get_size(x) for x in range(n *n))\n",
    "        for i,j in zeros:\n",
    "            mx = 1\n",
    "            vis = set()\n",
    "            for x,y in (i + 1,j),(i - 1,j),(i,j + 1),(i,j - 1):\n",
    "                if 0 <= x < n and 0 <= y < n and grid[x][y]:\n",
    "                    root = uf.find(x*n + y)\n",
    "                    if root not in vis:\n",
    "                        vis.add(root)\n",
    "                        mx += uf.get_size(x*n + y)\n",
    "            ans = max(ans,mx)\n",
    "        return ans\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self,n):\n",
    "        self.fa = list(range(n))\n",
    "        self.size = [1]*n\n",
    "    \n",
    "    def find(self,x):\n",
    "        if self.fa[x] != x:\n",
    "            self.fa[x] = self.find(self.fa[x])\n",
    "        return self.fa[x]\n",
    "\n",
    "    def union(self,x,y):\n",
    "        a,b = self.find(x),self.find(y)\n",
    "        if a != b:\n",
    "            if self.size[a] > self.size[b]:\n",
    "                a,b = b,a\n",
    "            self.fa[a] = b\n",
    "            self.size[b] += self.size[a]\n",
    "    \n",
    "    def get_size(self,x):\n",
    "        return self.size[self.find(x)]\n",
    "\n",
    "    def is_conn(self,x,y):\n",
    "        return self.find(x) == self.find(y)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestIsland(self, grid: List[List[int]]) -> int:\n",
    "        n = len(grid)\n",
    "        uf_p = [i for i in range(n * n)]\n",
    "        area = [0] * n * n\n",
    "\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                area[i * n + j] = grid[i][j]\n",
    "\n",
    "        def find(x):\n",
    "            if uf_p[x] == x:\n",
    "                return x\n",
    "            uf_p[x] = find(uf_p[x])\n",
    "            return uf_p[x]\n",
    "\n",
    "        def union(x, y):\n",
    "            if find(x) != find(y):\n",
    "                area[x] = area[y] = area[find(y)] = area[find(x)] = area[find(x)] + area[find(y)]\n",
    "            uf_p[find(x)] = find(y)\n",
    "\n",
    "        # 构造并查集\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] != 1:\n",
    "                    continue\n",
    "                if i - 1 >= 0 and grid[i - 1][j] == 1:\n",
    "                    union(i * n + j, (i - 1) * n + j)\n",
    "                if j - 1 >= 0 and grid[i][j - 1] == 1:\n",
    "                    union(i * n + j, i * n + (j - 1))\n",
    "\n",
    "        max_area_ = 0\n",
    "        max_area = [[1 for _ in range(n)] for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                max_area_ij = max_area[i][j]\n",
    "                try_to_link = set()\n",
    "                for i_, j_ in [(-1, 0), (0, -1), (1, 0), (0, 1)]:  # 上、左、下、右\n",
    "                    if (n > i + i_ >= 0 and n > j + j_ >= 0\n",
    "                            and find((i + i_) * n + j + j_) not in try_to_link  # 相邻岛未尝试连过\n",
    "                            and find((i + i_) * n + j + j_) != find(i * n + j)):  # 相邻岛不相连\n",
    "                        max_area_ij = max(max_area_ij, max_area_ij + area[find((i + i_) * n + j + j_)])\n",
    "                        try_to_link.add(uf_p[find((i + i_) * n + j + j_)])\n",
    "                max_area[i][j] = max(max_area_ij, area[i * n + j])\n",
    "                max_area_ = max(max_area_, max_area[i][j])\n",
    "\n",
    "        return max_area_"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestIsland(self, land: List[List[int]]) -> int:\n",
    "        '''\n",
    "        尝试使用类似记忆化的思想枚举每个连通块\n",
    "        '''\n",
    "        m,n=len(land),len(land[0])\n",
    "        def dfs(i,j):\n",
    "            fa[i*n+j]=pa\n",
    "            node.append((i,j))\n",
    "            vis[i][j]=True\n",
    "            for u,v in (i-1,j),(i+1,j),(i,j-1),(i,j+1):\n",
    "                if 0<=u<m and 0<=v<n and land[u][v] and not vis[u][v]:\n",
    "                    dfs(u,v)\n",
    "\n",
    "        ans=0\n",
    "        vis=[[False]*n for _ in range(m)]\n",
    "        size=[[0]*n for _ in range(m)]\n",
    "        fa=[i for i in range(m*n)]\n",
    "        for i,row in enumerate(land):\n",
    "            for j,v in enumerate(row):\n",
    "                node=[]\n",
    "                if v and not vis[i][j]:\n",
    "                    pa=i*n+j\n",
    "                    dfs(i,j)\n",
    "                    for (x,y) in node:\n",
    "                        size[x][y]=len(node)\n",
    "        ans=max(v for i,row in enumerate(size) for j,v in enumerate(row))\n",
    "        for i,row in enumerate(land):\n",
    "            for j,v in enumerate(row):\n",
    "                #关键点，每次都是把0变成1，所以连通块彼此独立\n",
    "                s=set()\n",
    "                if not v:\n",
    "                    res=1\n",
    "                    for u,v in (i-1,j),(i+1,j),(i,j-1),(i,j+1):\n",
    "                        if 0<=u<m and 0<=v<n and fa[u*n+v] not in s:\n",
    "                            s.add(fa[u*n+v])\n",
    "                            res+=size[u][v]\n",
    "                    ans=max(ans,res)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestIsland(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        def dfs(x, y, mark):\n",
    "            visited.add((x, y))\n",
    "            grid[x][y] = mark\n",
    "            cnt = 1\n",
    "            for newx, newy in [(x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1)]:\n",
    "                if 0 <= newx < m and 0 <= newy < n and (newx, newy) not in visited and grid[newx][newy] == 1:\n",
    "                    cnt += dfs(newx, newy, mark)\n",
    "            return cnt\n",
    "\n",
    "        mark = 2\n",
    "        dic = {}\n",
    "        visited = set()\n",
    "        is_allisland = True\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 0:\n",
    "                    is_allisland = False\n",
    "                if grid[i][j] == 1 and (i, j) not in visited:\n",
    "                    dic[mark] = dfs(i, j, mark)\n",
    "                    mark += 1\n",
    "        if is_allisland:\n",
    "            return m * n \n",
    "        res = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                temp = 1\n",
    "                mark_visited = set()\n",
    "                if grid[i][j] == 0:\n",
    "                    for newi, newj in [(i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)]:\n",
    "                        if 0 <= newi < m and 0 <= newj < n and grid[newi][newj] not in mark_visited and grid[newi][newj] != 0:\n",
    "                            temp += dic[grid[newi][newj]]\n",
    "                            mark_visited.add(grid[newi][newj])\n",
    "                res = max(temp, res)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestIsland(self, grid: List[List[int]]) -> int:\n",
    "        # 并查集 ---- 先把基础的模板写下来\n",
    "\n",
    "        def find(x):\n",
    "            if x != parent[x]:\n",
    "                parent[x] = find(parent[x])\n",
    "            return parent[x]\n",
    "\n",
    "        def union(x, y):\n",
    "            x_root = find(x)\n",
    "            y_root = find(y)\n",
    "            if x_root == y_root:\n",
    "                return False\n",
    "            if size[x_root] > size[y_root]:\n",
    "                x_root, y_root = y_root, x_root\n",
    "            parent[x_root] = y_root  # 将 x 并入 y 中\n",
    "            size[y_root] += size[x_root]\n",
    "            # 这里可以计算连通块的数目\n",
    "            # 连通块个数减一\n",
    "            return True\n",
    "\n",
    "        # 初始化 --- 求出每个岛屿的面积， 将属于同一个岛屿的陆地归到一个连通块中\n",
    "        n = len(grid)\n",
    "        parent = [i for i in range(n * n)]\n",
    "        size = [1] * (n * n)\n",
    "        for i, row in enumerate(grid):\n",
    "            for j, v in enumerate(row):\n",
    "                if v:\n",
    "                    for a, b in [[0, 1], [1, 0]]:\n",
    "                        x, y = i + a, j + b\n",
    "                        if 0 <= x < n and 0 <= y < n and grid[x][y]:\n",
    "                            union(x * n + y, i * n + j)\n",
    "        ans = max(size)\n",
    "        # 枚举 0 点  维护最大值\n",
    "        for i, row in enumerate(grid):\n",
    "            for j , v in enumerate(row):\n",
    "                if v == 0:\n",
    "                    connect = set()\n",
    "                    res = 1\n",
    "                    for a, b in [[0, 1], [0, -1], [1, 0], [-1, 0]]:\n",
    "                        x, y = i + a, j + b\n",
    "                        if 0 <= x < n and 0 <= y < n and grid[x][y]:\n",
    "                            root = find(x * n + y)\n",
    "                            if root not in connect:\n",
    "                                connect.add(root)\n",
    "                                res += size[root]\n",
    "                    ans = max(ans, res)\n",
    "        return ans\n",
    "\n",
    "       \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestIsland(self, grid: List[List[int]]) -> int:\n",
    "        n = len(grid) \n",
    "        p = [i for i in range(n*n+1)]\n",
    "        rank = [1] * (n * n+1)\n",
    "        def find(x):\n",
    "            if x == p[x]:\n",
    "                return x \n",
    "            p[x] = find(p[x]) \n",
    "            return p[x] \n",
    "        def un(x, y):\n",
    "            fx, fy = find(x), find(y)\n",
    "            if fx == fy:\n",
    "                return False \n",
    "            if rank[fx] < rank[fy]:\n",
    "                fx,fy = fy,fx \n",
    "            p[fy] =fx \n",
    "            rank[fx] += rank[fy]\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if grid[i][j]==1:\n",
    "                    if i + 1 < n and grid[i+1][j] == 1:\n",
    "                        un(i*n+j, (i+1)*n+j) \n",
    "                    if j + 1 < n and grid[i][j+1] == 1:\n",
    "                        un(i*n+j, i*n+j+1) \n",
    "        ans = 0 \n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 0:\n",
    "                    nset = set()\n",
    "                    for [ni, nj] in [[i+1,j], [i-1,j], [i,j+1],[i,j-1]]:\n",
    "                        if 0<=ni<n and 0<=nj<n and grid[ni][nj]==1:\n",
    "                            nset.add(find(ni*n+nj))\n",
    "                    tot = 1\n",
    "                    for x in nset:\n",
    "                        tot += rank[x]\n",
    "                    ans = max(ans, tot)\n",
    "        return ans if ans > 0 else max(rank) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "class Solution:\n",
    "    def largestIsland(self, grid: List[List[int]]) -> int:\n",
    "        # dfs 遍历所有岛，求出面积\n",
    "        area = Counter()\n",
    "        visited = set()\n",
    "        tag = [[0 for _ in range(len(grid[0]))] for _ in range(len(grid))]\n",
    "        def dfs(i,j):\n",
    "            area[t] += 1\n",
    "            tag[i][j] = t\n",
    "            visited.add((i,j))\n",
    "            for ni,nj in (i-1,j), (i,j-1), (i+1,j), (i,j+1):\n",
    "                if 0<=ni<=len(grid)-1 and 0<=nj<=len(grid[0])-1 and grid[ni][nj]==1 and (ni,nj) not in visited:\n",
    "                    dfs(ni,nj)\n",
    "        \n",
    "        for i in range(len(grid)):\n",
    "            for j in range(len(grid[0])):\n",
    "                if grid[i][j] == 1 and (i,j) not in visited:\n",
    "                    t = i*len(grid)+j+1\n",
    "                    dfs(i,j)\n",
    "        ans = max(area.values(), default=0)\n",
    "        # print(area)\n",
    "        for i in range(len(grid)):\n",
    "            for j in range(len(grid[0])):\n",
    "                if grid[i][j] == 0:\n",
    "                    new_area = 1\n",
    "                    connected = {0}\n",
    "                    for ni,nj in (i,j+1), (i,j-1), (i-1,j), (i+1,j):\n",
    "                        if 0<=ni<=len(grid)-1 and 0<=nj<=len(grid[0])-1:\n",
    "                            if tag[ni][nj] not in connected:\n",
    "                                new_area += area[tag[ni][nj]]\n",
    "                                connected.add(tag[ni][nj])\n",
    "                    ans = max(ans, new_area)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestIsland(self, grid: List[List[int]]) -> int:\n",
    "        f = {}\n",
    "        size = {}\n",
    "        def find(x):\n",
    "            f.setdefault(x, x)\n",
    "            if f[x] != x:\n",
    "                f[x] = find(f[x])\n",
    "            return f[x]\n",
    "\n",
    "        def union(x, y):\n",
    "            root_x = find(x)\n",
    "            root_y = find(y)\n",
    "            if root_x != root_y:\n",
    "                f[root_x] = root_y\n",
    "                size[root_y] += size[root_x]\n",
    "\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1:\n",
    "                    size[i * m + j] = 1\n",
    "                    for x, y in [[-1, 0], [0, -1]]:\n",
    "                        new_x = x + i\n",
    "                        new_y = y + j\n",
    "                        if 0 <= new_x < m and 0 <= new_y < n and grid[new_x][new_y] == 1:\n",
    "                            union(new_x * m + new_y, i * m + j)\n",
    "\n",
    "        ans = max(size.values() or [0])\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 0:\n",
    "                    visited = set()\n",
    "                    area = 1\n",
    "                    for x, y in [[0, -1], [0, 1], [1, 0], [-1, 0]]:\n",
    "                        new_x = x + i\n",
    "                        new_y = y + j\n",
    "                        if 0 <= new_x < m and 0 <= new_y < n and grid[new_x][new_y] == 1:               \n",
    "                            root = find(new_x * m + new_y)\n",
    "                            if root not in visited:\n",
    "                                visited.add(root)\n",
    "                                area += size[root]\n",
    "                    ans = max(ans, area)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestIsland(self, grid: List[List[int]]) -> int:\n",
    "\n",
    "        def find(x):\n",
    "            if p[x]!=x:\n",
    "                p[x]=find(p[x])\n",
    "            return p[x]\n",
    "        def merge(x,y):\n",
    "            px,py=find(x), find(y)\n",
    "            if px == py:\n",
    "                return\n",
    "            p[px]=py\n",
    "            size[py]+=size[px]\n",
    "\n",
    "        n = len(grid)\n",
    "        p = list(range(n * n))\n",
    "        size = [1] * (n * n)\n",
    "        for i, row in enumerate(grid):\n",
    "            for j, v in enumerate(row):\n",
    "                if v:\n",
    "                    for a, b in [[0, -1], [-1, 0]]:\n",
    "                        x, y = i + a, j + b\n",
    "                        if 0 <= x < n and 0 <= y < n and grid[x][y]:\n",
    "                            merge(x * n + y, i * n + j)\n",
    "        ans = max(size)\n",
    "        for i, row in enumerate(grid):\n",
    "            for j, v in enumerate(row):\n",
    "                if v == 0:\n",
    "                    vis = set()\n",
    "                    t = 1\n",
    "                    for a, b in [[0, -1], [0, 1], [1, 0], [-1, 0]]:\n",
    "                        x, y = i + a, j + b\n",
    "                        if 0 <= x < n and 0 <= y < n and grid[x][y]:\n",
    "                            root = find(x * n + y)\n",
    "                            if root not in vis:\n",
    "                                vis.add(root)\n",
    "                                t += size[root]\n",
    "                    ans = max(ans, t)\n",
    "        return ans\n",
    "        "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
